本文作者东泽，来自安比技术社区的小伙伴，目前就读于斯坦福大学，研究方向密码学。 SVP问题（Shortest Vector Problem）
一个Lattice中最常见的问题，就是最短向量问题（SVP，Shortest Vector Problem）。问题的定义是这样的：给定一个基为 观察发现，因为 图中给出了一个比较经典的例子，加入我们拥有一组格的基向量 当然，如果我们拿到的基不是很好，其实计算严格的SVP（即找出 在 图上显示的就是当 CVP问题（Closest Vector Problem）
Lattice中另一大常见的问题，就是最近向量问题（CVP，Closest Vector Problem）了。问题的定义是这样的：给定连续空间中任意的一个点 这里我们的约束距离 加上一个宽松的参数 SIVP问题（Shortest Independent Vectors Problem）
Lattice中第三大重要的问题，就是最短独立向量问题。问题定义：给定一个Lattice 这个图就很好的表达了在 学会了SVP，CVP，SIVP这三件套之后，就可以来了解一下如何通过Lattice来进行可靠的消息传输了。 我们要解决的问题是在一个有噪音的信道中可靠的传输信息（Reliable transmission of information over noisy channels）。结合Lattice的概念之后，其实实现起来很简单。 首先，我们把需要传输的消息映射到Lattice中的一个点上，即 在解决CVP问题的时候，我们还需要知道这个Lattice中最短向量 最后，SIVP问题在这里也有所适用。如果我们在传输的过程中为了压缩数据使用了向量量化（Vector Quantization）的方法，在重建向量的时候，需要用到SIVP的解来修复误差。 给定一个Lattice
CVP问题对于搜索的范围和结果的大小已经有所约束了，但是并没有约束一共有多少结果和范围究竟有多大。所以CVP问题又可以细分为两种主要的版本。1 BDD（Bounded Distance Decoding）问题
BDD问题规定了 ADD（Absolute Distance Decoding）问题
ADD问题则不同，规定了 我们之前提到的SVP，CVP，以及CVP下面的BDD，ADD，都是公认的很难在多项式时间内有效解决的难题。我们来看一看这些难题之间的关联性。
最近的二三十年来的各种paper逐渐的把这些难度的关系给证明了出来。具体的后面再详细研究。 上一部分的图中，我们发现ADD和SIVP问题被归为同一层（困难度）。这是因为经过一系列的变换，我们可以把ADD问题规约到SIVP问题上。 假设我们需要求解 因为我们是使用了取整的操作来找到格点的，所以这个解的格点到 分析Lattice问题的时候，几何结构是一个非常强有力的工具。 举个例子，在最简单的笛卡尔坐标系整数格 为什么
我们对把一个Lattice的基进行变换，找到一组非常接近垂直的基的过程，称之为Lattice Basis Reduction 。这一过程在LLL82这一篇中有详细的描述。 一个比较常见的Basis Reduction方法是Gram-Schmidt正交化过程。假设我们拥有一个格的基 在这个Lattice中，我们发现这两个基向量是不垂直的。接下来，我们尝试找到一组互相垂直的基 在图中的这个案例中，一共有两个基向量，即 确定了 随后，我们可以选取在这一条线上符合条件的一个向量作为 这样一来，我们就得到了一组新的相互垂直的基 之前说过，如果一个Lattice的基向量是互相垂直的（orthogonal），那么在这个Lattice中解决CVP问题是非常简单的。我们只需要根据这个点 对于没有垂直基的Lattice，比如说我们这里看到的 我们可以用这组垂直基 这样一来，我们可以把任意的一个点 当我们做取整操作的时候，因为几何形状的原因，最后的得到的结果格点和CVP问题的真正解会略有误差。比如我们看上图，如果 只要满足这一条件，那么我们通过取整操作就能解决CVP。如果落点在外圈圆的话，那么很有可能就会被取整到隔壁的格点上去，那么那个点就不是最近的了。 Babai86提出了Nearest Plane Algorithm，这一算法正式的指出了取整方法可以逼近CVP问题的答案。这个算法说明了，我们Gram-Schmidt拿到的 封面图来自unsplash，作者Markus Spiske
