格上的代数问题是容易计算的，例如判断一个向量是否在格中，计算格的行列式等。但是格上的几何问题一般都是困难的。例如上面所说的最短向量长度问题，尽管闵可夫斯基（Minkowski）第一理论给出了最短向量长度的上界，但是该方法不是构造性的，并没有给出方法去发现这样的最短格向量。事实上目前还没有算法能够发现该长度的短向量。

下面是一些著名的格上计算问题。其中SVP问题与CVP问题是这些计算问题中最著名的，也是这些计算问题中最困难的。这两个问题都与

有关，而且它们之间是相互等价的。

SVP（最短向量问题，Shortest Vector Problem） 输入格L，发现格L的最短向量。

CVP（最靠近向量问题，Closest Vector Problem）输入格L与一个目标向量t（目标向量未必在格中），发现最靠近t的一个格点v。

SIVP（最短线性无关向量组问题，Shortest Independent Vectors Problem）输入n维格L，发现格L中的n个线性无关的向量b1，b2，…，bn，使得

是短的。

SIVP问题与有关，SVP问题与CVP问题可以归约到SIVP问题，即如果解决了SVP问题或者CVP问题，则SIVP问题就可以被有效的解决。

目前还不知道如何在SVP问题与CVP问题上构造密码学函数，格密码学所依赖的主要计算问题就是SIVP问题。

上面这些问题的描述都是精确版本。在格密码学中，通常考虑这些问题的近似情况，用一个角标表示其近似因子。例如表示发现一个向量其长度至多为最短向量长度的倍。

密码学中还有一个常用的格上计算问题，它来自于问题。给一个格L和一个有理数r，有两种完全不同的情况：“Yes”情况，即< r；“No”情况，即> r。目标是判断给出的格L属于哪一种情况。

CVP问题还有一种特殊情况称为BDD（Bounded Distance Decoding problem）问题，即当格点与目标点的距离小于/2时，发现一个最靠近目标点的格点。如果该格点存在，则是唯一的。SIVP问题可以归约到BDD问题，即解决了SIVP问题就可以有效的解决BDD问题。这里要特别强调，格上BDD问题是通过其对偶格中上的一组短向量（即使用SIVP问题）进行解决的。这也是构建格上公钥密码学的基础。

问题的困难性 对于准确求解SVP问题，或者在多项式近似因子内近似求解，已知最好的算法需要运行时间为，算法的空间需求也为指数级。如果用多项式时间算法近似求解以上所有问题，能够获得的近似因子=，几乎是格的维数的指数级。所以对于近似因子是指数级=时，格上的计算问题是容易的，而对于小的近似因子，格上的计算问题是NP难题。

密码学主要建立在多项式近似因子之上，例如为= nc，其中c至少为1。对于这样的近似因子，格上的计算问题并不认为是NP困难的，但是仍然认为是困难的，因为已知最好的算法依然需要指数级时间，即使量子计算机目前也无法降低其运行时间。

一般来说，一个计算问题的复杂度有平均情况下的复杂度，也有最坏情况下的复杂度。最坏情况下的复杂度所花费的计算时间也是最多的，所以一个计算问题在最坏情况下的困难性也是最困难的。如果在最坏情况下即使以小概率破解了该问题的一个实例，则就能破解该问题的所有实例。格密码学将假设建立在格上计算问题的最坏情况下的困难性之上。以往密码学都是建立在平均情况的困难性假设之上，格密码学的特殊性质使得它非常具有吸引力。

格密码学假设：在最坏情况下求解格上的计算问题，没有多项式时间算法能够获得多项式近似因子。即对于任何可能的格，没有多项式时间算法能够获得多项式近似因子。需要注意的是当近似因子超过时，近似格问题将不再是NP难题，只有当近似因子更小时，例如时，近似格问题才是NP难题。

在上述格问题中，都是需要输入格，其意思就是输入格的基，通常用格的基来表示格。但是由于同一个格有很多基，因此有些基是“好的”，有些基是“坏”的。“好的”基意味着基中的向量是短的而且向量之间偏向于正交，“坏的”基意味着基中的向量是长的而且向量都在同一方向（或者相反方向）。对于“好的”基，以上格的困难问题就意味着容易求解。

===============================================================文章首发在微信公众号：btc201800http://weixin.qq.com/r/GC8UDDjEjmXxrXxv93oK (二维码自动识别)音频发布在喜马拉雅上“区块链杂谈 (第2季)“

宁波格密链网络科技有限公司，专注于区块链上的密码技术研发。