最短距离和连续极小值

除了行列式，格的另一个基本量是格上最短非零向量的长度，即格中最短距离，其定义为
λ1=min⁡x,y∈L,x≠y∥x−y∥=min⁡z∈L,z≠0∥z∥.\\begin{aligned} \\lambda_1 &= \\min_{\\bm{x,y} \\in \\mathcal{L}, \\bm{x} \\neq \\bm{y}} \\| \\bm{x} - \\bm{y} \\| \\\\ &= \\min_{\\bm{z} \\in \\mathcal{L}, \\bm{z} \\neq \\bm{0}} \\| \\bm{z} \\|. \\end{aligned} λ1​​=x,y∈L,x=ymin​∥x−y∥=z∈L,z=0min​∥z∥.​

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

同理可定义第二至第$n$连续极小λ2,…,λn\\lambda_2, \\dots, \\lambda_nλ2​,…,λn​。

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

定义1 在格$\mathcal{L}$中，第$i$连续极小值（$i=1,\dots ,n$） 为λi=min⁡{r:dimspan(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$个线性无关格向量的最小球的半径。

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

在整数格Zn\\mathbb{Z}^nZn中，有λ1=λ2=⋯=λn\\lambda_1 = \\lambda_2 = \\cdots = \\lambda_nλ1​=λ2​=⋯=λn​。一般而言，λ1≤λ2⋯≤λn\\lambda_1 \\leq \\lambda_2 \\cdots \\leq \\lambda_nλ1​≤λ2​⋯≤λn​。

距离函数和覆盖半径

对任意点t∈Rn\\bm{t} \\in \\mathbb{R}^nt∈Rn，记距离函数$\mu (\mathbf{t},\mathcal{L})$返回$\mathbf{t}$到最近格点的距离，即μ(x,L)=min⁡x∈L∥t−x∥\\mu(\\bm{x}, \\mathcal{L}) = \\min_{\\bm{x} \\in \\mathcal{L}} \\| \\bm{t} - \\bm{x} \\|μ(x,L)=minx∈L​∥t−x∥。

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

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

格的平滑参数

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

当$r$是无穷大时是最理想的状态。事实上，存在一个有限的r^\\hat{r}r^值可使$\mathbf{\gamma }+\mathbf{x}$趋近于完全均匀分布，有max⁡μ≤∥r^∥≤log⁡(n)⋅nλn\\max \\mu \\leq \\| \\hat{r} \\| \\leq \\log(n) \\cdot \\sqrt{n} \\lambda_nmaxμ≤∥r^∥≤log(n)⋅n​λn​。

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

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

致谢

• Simons格密码公开课官网

Mathematics of Lattices - Simons Institute for the Theory of Computing

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

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

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

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

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

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