格(Lattice)学习笔记之一:历史与基本概念

2020-07-21 16:37 栏目:经验之谈 来源:网络整理 查看()

格子的历史

长久以来,数学家们一直在研究格。代表人物有拉格朗日、高斯、闵可夫斯基等。近几十年来,格在密码学、通信和密码分析中有着巨大的应用价值,是一个非常热门的领域。

现代晶格时间轴:

1982年:LLL基归约定理

使用格进行密码分析

1996年:Ajtai-Dwork

首次将格中平均情况和最坏情况的复杂性联系起来

提出了由格构造的单向函数和CRHF函数

2002:发现了平均情况/最坏情况复杂性之间的关系,并且基于格的协议变得更加有效

2005年:雷格夫提出了LWE,并发现了它的量子阻力

提出了PKE、IBE、安倍、FHE等的可能性

什么是格子

格可以被认为是空间中许多规则分布的离散点。

格(Lattice)学习笔记之一:历史与基本概念

我们可以在这个格上做任何线性变换,然后我们可以得到一个新的格。

格(Lattice)学习笔记之一:历史与基本概念

晶格和基底(晶格和基底)

描述一个格的更好的方法是使用基向量。

格(Lattice)学习笔记之一:历史与基本概念

同样地,我们可以利用线性代数中学习到的基的变化,为这个格找到一组新的基。

格(Lattice)学习笔记之一:历史与基本概念

如果我们系统地定义格,我们可以说格是Rn空间中的离散可加子群。

格的基本属性

格(Lattice)学习笔记之一:历史与基本概念

同样,格的行列式也是由对应于——的基向量组成的同一个平行六面体体积。

格(Lattice)学习笔记之一:历史与基本概念

同样,我们改变一组基向量,我们也可以计算它的行列式。

格(Lattice)学习笔记之一:历史与基本概念

值得注意的是,无论我们如何改变基向量,行列式的大小,即由基向量组成的多面体的体积,是相同的。给定任意一组基向量,我们可以有效地找到格空间的行列式。

晶格密度

我们可以用格的行列式来度量这个格的格分布密度。

首先,我们将由基础向量的最后一部分组成的多面体的中心移动到原点。这样,空间p仍然保持相同的体积。

格(Lattice)学习笔记之一:历史与基本概念

然后,我们可以制作这个多面体的多个副本,然后把它翻译成格子中的每个点。这样,我们将得到p的许多副本,这些多面体可以平均划分整个多维空间Rn。

格(Lattice)学习笔记之一:历史与基本概念

这时,如果我们在这个空间中任意画一个球(多维空间是超球),那么我们就可以算出这个球覆盖了格中的多少个点。点数等于球体的体积,也就是晶格的密度。

格(Lattice)学习笔记之一:历史与基本概念

这个概念也很容易理解。我们球体中格点的数量与球体体积中多面体的数量大致相同。

直线

格(Lattice)学习笔记之一:历史与基本概念

距离函数和覆盖半径

给定任意点t(该点不需要在格子上),我们可以将距离函数u(t,L)定义为从该点到附近格子点的最短距离。

格(Lattice)学习笔记之一:历史与基本概念

用同样的方法,我们也可以左右移动t的位置,然后我们可以找到在这个格子中能得到的最大u。我们通常称这个最大值为覆盖半径。

格(Lattice)学习笔记之一:历史与基本概念

为什么这个最远的距离叫做覆盖半径?这其实很简单。我们可以假设在这个格子中,许多歌曲圆圈是以每个格子为中心画的。

格(Lattice)学习笔记之一:历史与基本概念

如果圆的半径逐渐扩大,那么所有的圆将逐渐开始覆盖整个Rn空间。

格(Lattice)学习笔记之一:历史与基本概念

格(Lattice)学习笔记之一:历史与基本概念

直到所有的圆完全覆盖所有的空间,此时的半径是我们之前得到的u。这是覆盖半径名称的来源。

晶格的光滑性

如果我们稍微改变上述覆盖圆的概念,假设我们不是在每个网格点上叠加一个圆,而是叠加一个随机噪声,其值在圆的范围内,那么当圆的半径达到覆盖半径时,网格本身将与其后面的连续空间Rn合并。

然而,如果仅在覆盖半径上,可以在图上发现,由于网格点之间的相互位置,噪声覆盖的分布非常不均匀。也就是说,叠加噪声后,Rn上的值分布不均匀。

如果我们想使价值的分布更均匀,我们需要更平滑。)格,即继续扩大圆的半径。理论上,当半径接近无穷大时,我们得到的分布是最完美和平均的。然而,当圆是无限的时候,这种构造就没有实际意义了。

格(Lattice)学习笔记之一:历史与基本概念

所以一般来说,我们将给出平滑半径的最大上限。最大上限由该格中距离最大的最短向量决定。因为当我们的半径大于最短向量时,圆会覆盖太多的点(因为最短的距离决定了点之间的距离),然后构造就失去了意义。

格(Lattice)学习笔记之一:历史与基本概念

闵可夫斯基凸集定理(凸体定理)

对于格,闵可夫斯基给出了一些有趣的定理。第一个定理用于寻找格点周围最近的其他格点,即凸集定理。

格(Lattice)学习笔记之一:历史与基本概念

众所周知,在整数格Zn中,由于从原点到所有下一个点的距离形成的空间正好是2n,所以任何凸集(集的表面不能有凹陷)只要其体积大于2n,就会溢出这个空间,然后覆盖一个非零格。鸽子洞原理可以形象地理解它。

下一步,如果我们用一个不规则的格来代替它,也就是说,把线性变换叠加在原来的锌上,这个定理仍然成立。

格(Lattice)学习笔记之一:历史与基本概念

格(Lattice)学习笔记之一:历史与基本概念

闵可夫斯基第二定理

格(Lattice)学习笔记之一:历史与基本概念

微信二维码
售前客服二维码

文章均源于网络收集编辑侵删

提示:币友交流QQ/WX群请联系客服加入!

郑重申明:资讯文章为网络收集整理,官方公告以外的资讯内容与本站无关!
虚拟币开发,虚拟币交易平台开发,山寨币交易平台开发 Keywords: 虚拟币开发 虚拟币交易平台开发 山寨币交易平台开发