什么是格？
在数学中有两个完全不同的对象都称为格，我们现在说的格是定义为向量空间的离散子空间。在此，离散意味着在格中不能存在任意彼此接近的两个向量。换句话说，存在一个正实数λ，使得格中的任何两个向量都不能小于距离λ。
子空间一词告诉我们，如果您的格中有两个向量，那么你可以几何地从另一个向量中减去另一个，而最终的位置将是格中的另一个向量。这意味着零向量始终在格中。
在视觉上，二维的格看起来像这样，每个点不是连续的，而是离散的：
距离产生美，格是具有很好性质的数学对象，因为它们可以用相对少量的数据来描述。通常使用的描述是给出格的基，基是由若干向量组成的。通过这些基础向量的整数线性组合来生成所有其他点。
每个格都有一个基，但它远不是唯一的，实际上每个格都有无限的数量，而且并不是所有的格都一样好用。回到我们的示例格，我们可以添加一些基，在这种情况下是向量对：
直观上，我们可以注意到蓝色和绿色的基向量比黄色或紫色的基向量要好看（向量比较短）。实际上，使用短向量意味着使用较少的存储来描述格。在二维空间中，求短向量并不是一个困难问题，可以使用Lagrange算法求短向量。但是随着维数的增加，在随机给出一个基的情况下，求解该问题将会变得非常困难。
格上的基本问题
这引出了格中的第一个基本困难的问题，即最短向量问题（SVP）。给定格的一个基，问题就是在格中找到一个非零向量，该向量的长度在所有非零格向量上最短。
再重复说一遍，必须找到一个长度为的向量，其中是λ的最大可能值，λ可以对上面所述的离散性进行解释。众所周知，对于随机归约来说，这个问题是NP困难问题（非确定性多项式困难问题）。
由于这个问题非常困难，自然要考虑这个问题的一个放宽问题，即近似最短向量问题。所谓近似问题，就是并不准确求出该问题，而是某一范围内。
这里，给了一个近似因子γ，只需要在长度不超过γ的格向量中找到一个非零向量。
在密码学中，人们经常考虑是多项式格维数范围之内的近似因子γ。目前已知最好的多项式时间内求解近似SVP问题的算法，其近似因子都是亚指数格维数范围内。也就说求解出的向量长度并不短，尽管在有限时间内。反之，如果你想求解出多项式格维数范围之内的近似因子γ，即求解出长度不超过γ的格向量中找到一个非零短向量，其求解时间将不是多项式时间了。
其实密码学家更感兴趣的是判断问题。下一期将解释该问题。