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-caseworst-case复杂度之间的关系，基于lattice的协议变得更加高效
2005：regev提出了lwe，并且发现其量子抵抗性
提出pke，ibe，abe，fhe等等的可能性
lattice是什么
lattice可以被想象成是一个空间中很多有规律分布的、离散的点。
我们可以对此lattice进行任意的线性变换（linear transformation）b，然后可以得到新的lattice。
lattice与bases（格与基）
更好的描述一个格的方法是使用基向量。
同理可得，我们可以用线性代数中学到的基变更（change of basis）给这个lattice找到一组新的基c。
如果系统性的定义一下lattice的话，那么我们可以说lattice是rn这个空间中的一个离散的、具有加法运算的子群（a discrete additive subgroup）。
lattice的基本属性
同理可得，一个lattice的determinant也是一样的——对应的基向量所组成的parallelepiped的体积。
同理，我们换了一组基向量，也可以计算它的determinant。
值得注意的是，无论我们怎么更换基向量，determinant的大小，即基向量组成的多面体的体积是相同的。给定任意的一组基向量，我们都可以有效的找到这个lattice空间的determinant。
lattice的密度
我们可以用一个lattice的determinant来衡量这个格的点阵分布的密度。
首先，我们把上一部分基向量组成的多面体的中心挪到原点上来。这样，空间p仍然保持相同的体积。
随后，我们可以把这个多面体复制多份，然后平移到每一个lattice中的点上。这样我们就会得到很多份p，并且这些多面体可以平分整个多维空间rn。
此时，我们如果在这个空间中任意的画一个球体（多维空间即超球体），然后可以数数看这个球体中覆盖了多少lattice里的点。点的数量平均于球体的体积，就是这个格的密度了。
这个概念理解起来也非常简单。我们的球体中有多少个lattice的点，其实大概和球体的体积中有多少个det（l）的多面体，这两个比例大致相同。
最短距离
距离函数（distance function）与覆盖半径（covering radius）
给定任意一个点t（这个点不需要在lattice上），我们可以定义距离函数u（t,l）为这个点到附近的lattice点的最短距离。
同理可得，我们也可以左右移动t的位置，然后就可以找到在这个lattice中可以得到的最大的u。我们一般称这个最大值叫覆盖半径（covering radius）。
为什么称这个最远距离为覆盖半径呢，其实很简单。我们可以假设在这个lattice中，以每个格点为圆心画很多歌圆。
如果逐渐把圆的半径扩大的话， 那么所有的圆就会逐渐开始覆盖整个rn空间。
直到所有的圆正好完美的覆盖了所有的空间的时候，这个时候的半径，就是我们之前得到的u了。这就是覆盖半径这一名字的由来。
lattice的smoothing
如果我们把上面的覆盖圆的概念稍微转换一下，假设我们不是在每个格点上叠加一个圆形，而是叠加一个圆形范围内取值的随机噪音，那么当圆的半径达到覆盖半径之后，这个lattice本身就和背后的连续空间rn合二为一了。
但是如果就只是在覆盖半径上的话，可以在图上发现，噪音覆盖的分布非常的不平均，因为格点之间相互的位置的问题。这也就是说，叠加了噪音之后，最后得到在rn上的取值分布也不平均。
如果想让取值分布更加平均的话，我们就需要更多的smooth（平滑化？）这个lattice，即继续扩大圆的半径。理论上当半径接近于无限大的时候，我们得到的分布是最完美、最平均的。但是当圆无限大了之后，这个构造就没有太多实际操作的意义了。
所以一般来说，我们都会给这个smoothing的半径一个最大上限。这个最大上限是由这个lattice中距离最大的最短向量来决定的。因为当我们的半径大于了这个最短向量之后，那么这个圆就会覆盖太多的点（因为最短距离决定了点到点之间的距离），然后这个构造就失去了意义。
minkowski凸集定理（convex body theorem）
对于lattice，minkowski给出了几个比较有意思的定理。第一个定理是用于寻找一个格点周围最近的其他格点的，即凸集定理。
在整数格zn中非常好理解，因为以原点出发到所有下一个点这段距离构成的空间，恰好就是2n，所以说任何凸集（集合的表面不能有凹陷）只要体积大于2n，那就一定会溢出这段空间，进而覆盖某个非0的格点。通过pigeonhole principle（鸽子洞原理）就可以很生动的理解了。
接下来，如果我们换成一个不规则的lattice，即在原有的zn上叠加线性变换，这个定理还是成立的。
minkowski第二定理