电商网站建设策划,python 做网站速度,百度指数官方,百度搜索引擎入口官网文章目录最短距离和连续极小值距离函数和覆盖半径格的平滑参数致谢最短距离和连续极小值
除了行列式#xff0c;格的另一个基本量是格上最短非零向量的长度#xff0c;即格中最短距离#xff0c;其定义为 λ1minx,y∈L,x≠y∥x−y∥minz∈L,z≠0∥z∥.\begin{aligned} …
文章目录最短距离和连续极小值距离函数和覆盖半径格的平滑参数致谢最短距离和连续极小值
除了行列式格的另一个基本量是格上最短非零向量的长度即格中最短距离其定义为 λ1minx,y∈L,x≠y∥x−y∥minz∈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} λ1x,y∈L,xymin∥x−y∥z∈L,z0min∥z∥. 如上图所示两两格点构成的向量都可以通过平移得到起始点为原点的向量通过找到距离原点最近的格点即可计算出格中最短距离。格中最短距离也称为第一连续极小记为λ1\lambda_1λ1。
同理可定义第二至第nnn连续极小λ2,…,λn\lambda_2, \dots, \lambda_nλ2,…,λn。
在二维格上可以用多项式时间算法求解出λ1\lambda_1λ1但在多维格上求解λ1\lambda_1λ1则十分困难。注意给定一组格基最短向量不一定是格基之一。
定义1 在格L\mathcal{L}L中第iii连续极小值i1,…,ni1,\dots, ni1,…,n 为λimin{r:dimspan(B(r)∩L)≥i}\lambda_i \min \{ r : \mathrm{dim} ~ \mathrm{span}(\mathcal{B}(r) \cap \mathcal{L}) \geq i \}λimin{r:dim span(B(r)∩L)≥i}。
在定义1中B(r)\mathcal{B}(r)B(r)表示半径为rrr的超球体Ball该超球体与格L\mathcal{L}L交集产生的向量张成span\mathrm{span}span的空间的维度dim\mathrm{dim}dim为iii。换而言之第iii连续极小值即包含至少iii个线性无关格向量的最小球的半径。
把球的中心放在原点若球中有非零格向量那么球中不止一个格向量。以上图为例红色区域包含了一个非零格向量以及它的逆向量但这二者在同一条直线上仅张成一维空间该超球体的半径是λ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记距离函数μ(t,L)\mu(\bm{t}, \mathcal{L})μ(t,L)返回t\bm{t}t到最近格点的距离即μ(x,L)minx∈L∥t−x∥\mu(\bm{x}, \mathcal{L}) \min_{\bm{x} \in \mathcal{L}} \| \bm{t} - \bm{x} \|μ(x,L)minx∈L∥t−x∥。
通过移动t\bm{t}t可以找到μ\muμ的最大值称为覆盖半径即μ(L)maxt∈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)。以下图为例t\bm{t}t从①移动至②再移动至③此时无论t\bm{t}t再怎么移动都会减小μ\muμ的值故μ\muμ在步骤③时达到最大。 以下图为例将所有格点作为球心不断增大球的半径rrr当半径rrr超过12λ1\frac{1}{2} \lambda_121λ1时这些球开始互相覆盖而当空间中所有点都被这些球覆盖时rrr刚好等于μ\muμ的最大值名称“覆盖半径”由此而来。想象一下在下图的第三张子图里若再移动蓝色点t\bm{t}t均会落在球的内部从而使μ\muμ变小。 格的平滑参数
假设噪声γ\bm{\gamma}γ随机采样自均匀分布U([0,r]n)\mathrm{U}([0, r]^n)U([0,r]n)记格点为x∈L\bm{x} \in \mathcal{L}x∈L为使γx\bm{\gamma} \bm{x}γx的分布看起来与U(Rn)\mathrm{U}(\mathbb{R}^n)U(Rn)无异要使rrr足够大。以上图为例γx\bm{\gamma} \bm{x}γx的出现频数用红色深浅表示当rrr太小时有些地方是空白色随着rrr的增大有些区域红色的深浅程度不一当rrr无穷大时所有区域颜色一样。
当rrr是无穷大时是最理想的状态。事实上存在一个有限的r^\hat{r}r^值可使γx\bm{\gamma} \bm{x}γ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。
注下面笔记属于个人猜测高斯噪声这块公开课讲得比较模糊强烈建议查阅原始论文。
球的半径要取得很大是因为它的边界十分明显。为解决该问题可以使球心到边界逐渐平滑即采用球状高斯分布进行平滑从而得到高斯噪声。以下图为例高斯平滑缩小了rrr值。对半径对应向量的每个分量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ηϵ由一个错误参数ϵ\epsilonϵ决定ϵ\epsilonϵ表示当前噪声分布和均匀噪声分布之间的差异。 致谢
Simons格密码公开课官网
Mathematics of Lattices - Simons Institute for the Theory of Computing
哔哩哔哩中英双语视频字幕组重庆大学大数据与软件学院 后量子密码研究小组
【中英字幕】Simons格密码讲座第1讲格的数学定义_哔哩哔哩_bilibili
其它格密码讲解课程和博文
格密码入门课程_哔哩哔哩_bilibili
格密码的基础概念_唠嗑的博客-CSDN博客_格密码
格Lattice基础一_Amire0x的博客-CSDN博客_两组格基生成同一个格的充要条件
