当前位置：首页 > news >正文

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

news 2025/7/20 6:31:24

文章目录

最短距离和连续极小值
距离函数和覆盖半径
格的平滑参数
致谢

最短距离和连续极小值

除了行列式，格的另一个基本量是格上最短非零向量的长度，即格中最短距离，其定义为
$λ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\lambda_1$ 。

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

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

定义1 在格 $L\mathcal{L}$ 中，第 $i$ 连续极小值（ $i=1,…,ni=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 \}$ 。

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

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

在这里插入图片描述

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

距离函数和覆盖半径

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

通过移动 $t\bm{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})$ 。以下图为例， $t\bm{t}$ 从①移动至②再移动至③，此时无论 $t\bm{t}$ 再怎么移动都会减小 $μ\mu$ 的值，故 $μ\mu$ 在步骤③时达到最大。

在这里插入图片描述

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

在这里插入图片描述

格的平滑参数

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

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

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

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