格密码LLL算法：如何解决最短向量SVP问题（2）

一. 约化基令为约化基，可得。当时，结论可化简为。证明：

唠嗑！

3216人浏览 · 2022-03-29 17:08:49

唠嗑！ · 2022-03-29 17:08:49 发布

4.1 算法迭代的次数与M呈现多项式时间关系。

4.2 算法每次迭代的时间与M呈现多项式时间关系。

结论

系列文章：

格密码LLL算法：如何解决最短向量SVP问题（1）-CSDN博客

格密码LLL算法：如何解决最短向量SVP问题（3）（完结篇）-CSDN博客

一. LLL约化基的第一条向量

如果 $b_1,\ldots,b_n\in R^n$ 为某 $\delta-LLL$ 约化基，那么LLL约化基的第一条向量是相对短的，如下：

$||b_1||\leq (\frac{2}{\sqrt{4\delta-1}})^{n-1}\lambda_1(L)$

当 $\delta=\frac{3}{4}$ 时，结论简化为 $\lVert b_1\rVert\leq2^{\frac{n-1}{2}}\lambda_1(L)$ ，此定义可以看成LLL约化基的必备性质之一。

证明：

给定任意格基 $b_1,\ldots,b_n,$ 依据格密码的基本理论，可得：

$\lambda_1(L)\geq min_i\lVert\tilde b_i\rVert$

由此可归纳出：

上式中的最后一个等号遵循了 $\tilde b_1=b_1$ 。当i遍历所有的取值时，可得：

加入格中最小值min的性质，可得：

到此证明完毕。

对此性质的理解：该约化基性质进一步限制了SVP问题的下限，当确定了 $\delta-LLL$ 约化基，就可以输出第一条向量，该向量的长度就可以作为SVP问题的近似解，近似比为 $2^{(n-1)/2}$ 。

二. LLL算法

第一张照片拍摄于1982年2月27日，第二张照片拍摄于2007年6月29日。从左到右依次为Peter van Emde Boas, Laszlo Lovasz, Hendrik Lenstra, Arjen Lenstra。

LLL算法的具体流程如下：

输入：整数格基 $b_1,\cdots,b_n\in Z^n$

第一步：计算正交基 $\tilde b_1,\ldots,\tilde b_n$

第二步：约化步骤。如下：

for i=2 to n

for j=i-1 to 1

$b_i\leftarrow b_i-c_{i,j}b_j\quad c_{i,j}=\lfloor\langle b_i,\tilde b_j\rangle /\langle \tilde b_j,\tilde b_j\rangle\rfloor$

第三步：置换步骤。如下：

若存在 $\delta \lVert\tilde b_i\rVert^2>\lVert\mu_{i+1}\tilde b_i+\tilde b_{i+1}\rVert^2$ ，则置换 $b_i$ 和 $b_{i+1}$ 。

并返回到第一步；

输出： $b_1,\ldots,b_n$

备注：此算法中 $\lfloor\,\,\rfloor$ 符号代表取最接近的整数，例如 $\lfloor\,3.3\,\rfloor=3,\lfloor\,3.8\,\rfloor=4$ ，且对任意实数取整，都有如下结论：

$|x-\lfloor x\rfloor|\leq \frac{1}{2}$

对此算法流程的理解：第三步的置换步骤保证输出的结果满足LLL约化基的性质2。第二步的约化步骤保证满足LLL约化基的性质1。如果将上述过程进行简化的话，可得如下：

在约化迭代时，仅仅操作了列变换 $b_i\leftarrow b_i+ab_j,i>j,a\in Z$ ，所以保证了整个过程的Gram-Schmidt正交基不变。有两个for对应内循环和外循环，当外循环处在第i轮迭代时，对于j<i，取整的操作可以保证 $b_i$ 在 $\tilde b_j$ 上的投影最大值不超过 $\frac{1}{2}\lVert\tilde b_j\rVert$ ，通过线性代数中矩阵的相减运算也可以得到此结论，此处不做过多赘述。

考虑外循环迭代到第i次，内循环迭代到j=2时为例子，矩阵B如下：

当j=2时，相当于每一列都减去整数倍的第二列，以此来保证每一列的第二个数的值最大不超过 $\frac{1}{2}||\tilde b_2||$ ，以此迭代类推。

三. LLL算法的正确性

LLL算法输出的 $\delta-LLL$ 约化基与相应正交基形成的格一样，且输出满足约化基的两个性质。

证明：

证明的关键是要说明此算法的输出满足 $\delta-LLL$ 约化基的两条性质且还是原格L(B)的格基。在进行置换操作时，就保证了算法的输出满足LLL约化基的性质2。在进行约化迭代操作时，仅仅进行了矩阵的基础列操作，此举不会改变格，如下：

$b_i\leftarrow b_i+ab_j,\quad i\neq j,a\in Z$

当i>j，考虑外循环的第i次迭代中的内循环第j次迭代时， $\lvert \mu_{i,j}\rvert$ 有如下结论：

第一个等号依据规约步骤的理解。最后一个不等号依据向量与投影相乘的结论：

$\langle b_j,\tilde b_j\rangle=\langle\tilde b_j,\tilde b_j\rangle$

到此，分析完毕。

四. 分析算法运行的时间

算法总运行时间的分析分成两步，第一步需要限定总迭代的次数，第二步需要限定单次迭代所需要的时间。两步都是多项式时间，才能证明此算法的总运行时间与输入的规模之间呈现多项式关系。对于输入的n个向量，每个向量至少需要一个比特位来表示，所以n个向量至少需要n个比特位来表示。对于长度为r的向量，表示此长度需要 log r 比特位，例如长度为8的向量，至少需要log(8)=3个比特位来表示。所以给定输入规模的表达式如下：

$M=max\lbrace n,log(max_i||b_i||)\rbrace$

最终算法的总运行时间是关于M的多项式关系，后续的分析也是基于此。

4.1 算法迭代的次数与M呈现多项式时间关系。

证明：

在计算机中为了方便表示格基，可以将任意格基单一映射到某个整数，该映射函数可以取名为“potential function”。

给定 $B=\lbrace b_1,\cdots,b_n\rbrace$ 为格 $\Lambda$ 的格基,定义子格 $D_B$ 如下：

令 $\Lambda_i$ 代表格基 $b_1,\cdots,b_i$ 形成的格，理解上子格 $D_B$ 如下：

$D_{B,i}=det\,\Lambda_i$

易得，初始值满足如下不等式：

$D_{B,0}\leq(max_i||b_i||)^{n(n+1)/2}$

该初始值的对数运算满足M的多项式关系。在递归操作时，不改变正交基形成的格，所以 $D_B$ 也是不变的，所以需要将重心放在置换操作步骤上。

当 $b_i$ 和 $b_{i+1}$ 进行置换时，令 $\Lambda_i',\, D'_{B,i}$ 分别代表置换后的新值。由此可得：

此运算最后一个不等式遵循置换操作的性质。

此结果说明，在每次置换迭代时， $D_B$ 都会缩小 $\sqrt{\delta}$ 倍，一直迭代到1时停止，由此可计算迭代次数如下：

上述运算过程需要使用到换底公式，如下：

$log_a b=\frac{log_2b}{log_2a},\quad log_{\frac{1}{a}}b=log_a(\frac{1}{b})$

对于任意的常数 $\delta<1$ （根据之前的理解 $\delta$ 取值在1/4到3/4之间），此迭代次数都是关于M的多项式关系。

证明完毕。

取一个最接近1的 $\delta=\frac{1}{4}+(\frac{3}{4})^{\frac{n}{n-1}}$ ，此时的运行时间也是多项式关系的。此时对应的则为LLL算法输出的最接近的近似比值为 $(\frac{2}{\sqrt3})^n$ ，此比值可以参照第一条性质进行运算理解，如果想进一步获得更好的比值，则需要用到Schnorr算法。