格理论与密码学--格基约减算法与实现(四)

二维格中的高斯约减算法,以及著名的LLL算法,该算法能够解决某些维数较低的格中的SVP问题和CVP问题。三随着格维数的增高,该算法的运行效果也随之减弱,以至于对高维度的格来说,即使LLL算法,也无法很好地解决SVP和CVP问题。所以大多数基于格理论的密码系统的安全性,都依赖于LLL算法以及其他格基约减算法能否高效解决apprSVP和apprCVP问题的困难性。

4.1 二维格中的高斯格基约减算法

高斯提出了如何在二维格中找出一组优质基的算法,这个算法的根本思想是:从一个基向量中交替减去另一个基向量的倍数,直到再没有更好的改进为止。没有更好的改进,就是没事算法中的一个特定的条件要求。

给定一个二维格$L \subset R^2$,它的一组基向量为$v_1$和$v_2$,并假设$||v_1|| < ||v_2||$。这个条件很容易实现,因为即使不能够直接满足上述条件,只需要将$v_2$和$v_2$交换位置即可。然后通过从向量$v_2$中减去$v_1$的倍数来达到减少$v_2$的目的。若可以从$v_2$中减去$v_1$任意倍数,则可以利用如下式中的$v^{\ast}_2$来代替$v_2$:

$v_2^{\ast} = v_2 - \frac{v_1 \cdot v_2}{||v1||^2} v_1$

由上式可以看出,向量$v^{\ast}_2$和向量$v_1$是正交的,并且向量$v^{\ast}_2$就是$v_2$在$v_1$证据补上的投影,如下图:

但上述做法在实际中并不可行,因为通过上式计算出来的向量$v^{\ast}_2$很可能根本不在格$L$中。所以,在实际应用中只允许从向量$v_2$中减去$v_1$的整数倍。为了达到跟上式相近的结果,利用下式的向量来取代$v_2$:

$v_2 - m v_1, m = \lceil \frac{v_1 \cdot v_2}{||v1||^2} \rceil$

如果$v_2$仍旧比$v_1$长,那么算法结束;否则,交换向量$v_1$和$v_2$,然后重复上述过程。高斯证明了这个过程可以在有限步后结束,并且最终的基向量具有良好的正交性质。算法4.1对上述程序给出了严格的描述。

更准确地说,当这个算法终止的时候,向量$v_1$就是格$L$中最短的非零向量。因此算法4.1很好地解决了SVP问题。

例4.1


4.2 LLL格基约减算法及其衍生和变形

4.2.1 LLL格基约减算法

高斯格基约算法给出了一个在二维格中找到最短非零向量的有效方法。但是这个方法具有一定的局限性,因为随着格维数的增加,寻找最短向量也变得越来越困难。1982年,Lenstra、Lenstra和Lovasz提出了著名的LLL算法。该算法思想源于Lagrange、Gauss、Hermite、Korkine-Zolotareff等的二次型理论及Minkovski的数的几何理论。

给定格$L$的一组基$\lbrace v_1,\dots, v_n\rbrace$,然后对他进行约减。约减的主要目的是将这组任意给定的基转化为一组正交性较好的优质基,并使得这个优质基中的各个向量尽量短。即,首先要得到能够通过算法找到的最短向量,然后,找到比这个最短向量稍长一点的向量,依次类推,直到最后找到这组基中的最后一个向量为止。或者,要使得在这个优质基中的向量之间具有相当好的正交性,即两个向量的点乘$v_i \cdot v_j$尽可能地接近零。

根据Hadamard不等式能够得到:

$delL = vol(F) \leq ||v_1||||v_2||\dots||v_n||$

zxp wechat
欢迎关注微信公众号!