格密码学习笔记（二）：连续极小、覆盖半径和平滑参数

最短距离和连续极小值

除了行列式，格的另一个基本量是格上最短非零向量的长度，即格中最短距离，其定义为
$$\begin{array}{rl}{\lambda }_1& =\underset{\mathbf{x},\mathbf{y}\in \mathcal{L},\mathbf{x}\ne \mathbf{y}}{\min }\Vert \mathbf{x}-\mathbf{y}\Vert \\ & =\underset{\mathbf{z}\in \mathcal{L},\mathbf{z}\ne 0}{\min }\Vert \mathbf{z}\Vert .\end{array}$$

如上图所示，两两格点构成的向量都可以通过平移得到起始点为原点的向量，通过找到距离原点最近的格点即可计算出格中最短距离。格中最短距离也称为第一连续极小，记为${\lambda }_1$。

同理可定义第二至第$n$连续极小${\lambda }_2,\dots ,{\lambda }_n$。

在二维格上，可以用多项式时间算法求解出${\lambda }_1$，但在多维格上求解${\lambda }_1$则十分困难。注意，给定一组格基，最短向量不一定是格基之一。

定义1 在格$\mathcal{L}$中，第$i$连续极小值（$i=1,\dots ,n$） 为 λ i = min ⁡ { r : d i m s p a n ( B ( r ) ∩ L ) ≥ i } \lambda_i = \min \{ r : \mathrm{dim} ~ \mathrm{span}(\mathcal{B}(r) \cap \mathcal{L}) \geq i \} λi​=min{r:dim span(B(r)∩L)≥i}。

在定义1中，$\mathcal{B}(r)$表示半径为$r$的超球体（Ball），该超球体与格$\mathcal{L}$交集产生的向量张成（$\mathrm{span}$）的空间的维度（$\dim$）为$i$。换而言之，第$i$连续极小值即包含至少$i$个线性无关格向量的最小球的半径。

把球的中心放在原点，若球中有非零格向量，那么球中不止一个格向量。以上图为例，红色区域包含了一个非零格向量以及它的逆向量，但这二者在同一条直线上，仅张成一维空间，该超球体的半径是${\lambda }_1$。而以下图为例，一个更大的超球体包含了4个非零格向量，可以张成二维空间，该超球体的半径是${\lambda }_2$。

在整数格${\mathbb{Z}}^n$中，有${\lambda }_1={\lambda }_2=\cdots ={\lambda }_n$。一般而言，${\lambda }_1\le {\lambda }_2\cdots \le {\lambda }_n$。

距离函数和覆盖半径

对任意点$\mathbf{t}\in {\mathbb{R}}^n$，记距离函数$\mu (\mathbf{t},\mathcal{L})$返回$\mathbf{t}$到最近格点的距离，即$\mu (\mathbf{x},\mathcal{L})={\min }_{\mathbf{x}\in \mathcal{L}}\Vert \mathbf{t}-\mathbf{x}\Vert$。

通过移动$\mathbf{t}$可以找到$\mu$的最大值，称为覆盖半径，即$\mu (\mathcal{L})={\max }_{\mathbf{t}\in \mathrm{span}(\mathcal{L})}\mu (\mathbf{t},\mathcal{L})$。以下图为例，$\mathbf{t}$从①移动至②再移动至③，此时无论$\mathbf{t}$再怎么移动都会减小$\mu$的值，故$\mu$在步骤③时达到最大。

以下图为例，将所有格点作为球心，不断增大球的半径$r$，当半径$r$超过$\frac{1}{2}{\lambda }_1$时这些球开始互相覆盖，而当空间中所有点都被这些球覆盖时$r$刚好等于$\mu$的最大值，名称“覆盖半径”由此而来。想象一下，在下图的第三张子图里，若再移动蓝色点$\mathbf{t}$均会落在球的内部从而使$\mu$变小。

格的平滑参数

假设噪声$\mathbf{\gamma }$随机采样自均匀分布$\mathrm{U}([0,r{]}^n)$，记格点为$\mathbf{x}\in \mathcal{L}$，为使$\mathbf{\gamma }+\mathbf{x}$的分布看起来与$\mathrm{U}({\mathbb{R}}^n)$无异，要使$r$足够大。以上图为例，$\mathbf{\gamma }+\mathbf{x}$的出现频数用红色深浅表示，当$r$太小时有些地方是空白色，随着$r$的增大有些区域红色的深浅程度不一，当$r$无穷大时所有区域颜色一样。

当$r$是无穷大时是最理想的状态。事实上，存在一个有限的$\hat{r}$值可使$\mathbf{\gamma }+\mathbf{x}$趋近于完全均匀分布，有$\max \mu \le \Vert \hat{r}\Vert \le \log (n)\cdot \sqrt{n}{\lambda }_n$。

注：下面笔记属于个人猜测，高斯噪声这块公开课讲得比较模糊，强烈建议查阅原始论文。

球的半径要取得很大是因为它的边界十分明显。为解决该问题，可以使球心到边界逐渐平滑，即采用球状高斯分布进行平滑，从而得到高斯噪声。以下图为例，高斯平滑缩小了$r$值。对半径对应向量的每个分量${\mathbf{v}}_i$，应使得$\Vert {\mathbf{v}}_i\Vert \approx {\eta }_{ϵ}\le \log (n){\lambda }_n$，仅略大于${\lambda }_n$，此处${\eta }_{ϵ}$被称为平滑参数。一般而言，${\eta }_{ϵ}$由一个错误参数$ϵ$决定，$ϵ$表示当前噪声分布和均匀噪声分布之间的差异。

致谢

• Simons格密码公开课官网

Mathematics of Lattices - Simons Institute for the Theory of Computing

• 哔哩哔哩中英双语视频（字幕组：重庆大学大数据与软件学院 后量子密码研究小组）

【中英字幕】Simons格密码讲座第1讲：格的数学定义_哔哩哔哩_bilibili

• 其它格密码讲解课程和博文

格密码入门课程_哔哩哔哩_bilibili

格密码的基础概念_唠嗑！的博客-CSDN博客_格密码

格（Lattice）基础（一）_Amire0x的博客-CSDN博客_两组格基生成同一个格的充要条件