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

Lattice的历史

Lattice(格)在很早以前就被各大数学家研究了一遍。代表人物有Lagrange,Gauss和Minkowski等等。最近的几十年内,Lattice密码学、通讯、密码分析上有了很大的应用价值,是非常火的一个领域。

近代Lattice时间线:

1982:LLL basis reduction theorem


使用Lattice来做Cryptanalysis

1996:Ajtai-Dwork


第一次把Lattice中Average-case与Worst-case的复杂度问题关联起来


提出了使用Lattice构造的One-way Function与CRHF(Collision Resistant Hash Function)

2002:找到了Average-case/worst-case复杂度之间的关系,基于Lattice的协议变得更加高效

2005:Regev提出了LWE,并且发现其量子抵抗性


提出PKE,IBE,ABE,FHE等等的可能性





Lattice是什么

Lattice可以被想象成是一个空间中很多有规律分布的、离散的点。

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

我们可以对此Lattice进行任意的线性变换(Linear Transformation)B,然后可以得到新的Lattice。

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

Lattice与Bases(格与基)

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


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

同理可得,我们可以用线性代数中学到的基变更(Change of basis)给这个Lattice找到一组新的基C。

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

如果系统性的定义一下Lattice的话,那么我们可以说Lattice是Rn这个空间中的一个离散的、具有加法运算的子群(A discrete additive subgroup)。

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

同理可得,一个Lattice的Determinant也是一样的——对应的基向量所组成的Parallelepiped的体积。

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

同理,我们换了一组基向量,也可以计算它的Determinant。

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

值得注意的是,无论我们怎么更换基向量,Determinant的大小,即基向量组成的多面体的体积是相同的。给定任意的一组基向量,我们都可以有效的找到这个Lattice空间的Determinant。

Lattice的密度

我们可以用一个Lattice的Determinant来衡量这个格的点阵分布的密度。

首先,我们把上一部分基向量组成的多面体的中心挪到原点上来。这样,空间P仍然保持相同的体积。


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

随后,我们可以把这个多面体复制多份,然后平移到每一个Lattice中的点上。这样我们就会得到很多份P,并且这些多面体可以平分整个多维空间Rn。

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

此时,我们如果在这个空间中任意的画一个球体(多维空间即超球体),然后可以数数看这个球体中覆盖了多少Lattice里的点。点的数量平均于球体的体积,就是这个格的密度了。

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

这个概念理解起来也非常简单。我们的球体中有多少个Lattice的点,其实大概和球体的体积中有多少个det(L)的多面体,这两个比例大致相同。

最短距离


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

距离函数(Distance Function)与覆盖半径(Covering Radius)

给定任意一个点t(这个点不需要在Lattice上),我们可以定义距离函数u(t,L)为这个点到附近的Lattice点的最短距离。


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

同理可得,我们也可以左右移动t的位置,然后就可以找到在这个Lattice中可以得到的最大的u。我们一般称这个最大值叫覆盖半径(Covering Radius)。

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

为什么称这个最远距离为覆盖半径呢,其实很简单。我们可以假设在这个Lattice中,以每个格点为圆心画很多歌圆。

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

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

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

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

直到所有的圆正好完美的覆盖了所有的空间的时候,这个时候的半径,就是我们之前得到的u了。这就是覆盖半径这一名字的由来。

Lattice的Smoothing

如果我们把上面的覆盖圆的概念稍微转换一下,假设我们不是在每个格点上叠加一个圆形,而是叠加一个圆形范围内取值的随机噪音,那么当圆的半径达到覆盖半径之后,这个Lattice本身就和背后的连续空间Rn合二为一了。

但是如果就只是在覆盖半径上的话,可以在图上发现,噪音覆盖的分布非常的不平均,因为格点之间相互的位置的问题。这也就是说,叠加了噪音之后,最后得到在Rn上的取值分布也不平均。

如果想让取值分布更加平均的话,我们就需要更多的Smooth(平滑化?)这个Lattice,即继续扩大圆的半径。理论上当半径接近于无限大的时候,我们得到的分布是最完美、最平均的。但是当圆无限大了之后,这个构造就没有太多实际操作的意义了。


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

所以一般来说,我们都会给这个Smoothing的半径一个最大上限。这个最大上限是由这个Lattice中距离最大的最短向量来决定的。因为当我们的半径大于了这个最短向量之后,那么这个圆就会覆盖太多的点(因为最短距离决定了点到点之间的距离),然后这个构造就失去了意义。

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

Minkowski凸集定理(Convex body theorem)

对于Lattice,Minkowski给出了几个比较有意思的定理。第一个定理是用于寻找一个格点周围最近的其他格点的,即凸集定理。


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

在整数格Zn中非常好理解,因为以原点出发到所有下一个点这段距离构成的空间,恰好就是2n,所以说任何凸集(集合的表面不能有凹陷)只要体积大于2n,那就一定会溢出这段空间,进而覆盖某个非0的格点。通过Pigeonhole Principle(鸽子洞原理)就可以很生动的理解了。

接下来,如果我们换成一个不规则的Lattice,即在原有的Zn上叠加线性变换,这个定理还是成立的。

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

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

Minkowski第二定理

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

关键词: Lattice  密码学  

该内容来自于互联网公开内容,非区块链原创内容,如若转载,请注明出处:https://htzkw.com/archives/28862

联系我们

aliyinhang@gmail.com