本文详细了介绍原始格基规约算法，并简单介绍目前对算法的改进。这些改进算法非常实用，被广泛应用于密码分析中。

阅读本篇前需要先了解格论，可以先看看格基规约算法：数学基础

 

原始格基规约算法

高斯算法

在18到19世纪间，拉格朗日和高斯先后提出了一种二维格基规约算法，现今称为高斯算法。下面介绍原始的高斯算法。

算法描述

以下内容基本来自 Lattice Basis Reduction: An Introduction to the LLL Algorithm and its Application .

首先先给出算法中出现的概念和符号。

• 最小基：设$\, \mathbf{x},\mathbf{y}\,$是二维格$\,\mathcal{L}\subset\mathbb{R}^2\,$的一组基。若$\, \mathbf{x},\mathbf{y}\,$满足$\,\left | \mathbf{x}\right | =\lambda_1\left(\mathcal{L}\right)\,$ 且$\, \mathbf{y}\,$是与$\, \mathbf{x}\,$线性无关的一个最短向量，则称$\, \mathbf{x},\mathbf{y}\,$是最小的(minimal)。最小基也被称为Minkowski约化基。

• 取整：记$\, \lceil\mu\rfloor\,$为距$\,\mu\,$最近的整数，即$\, \lceil\mu\rfloor=\left\lceil\mu-\frac{1}{2}\right\rceil\,$。我们规定对于整数$\,n\,$，$\lceil n+\frac{1}{2}\rfloor\,$的值为$\, n\,$ 。

下面给出高斯算法的伪代码描述。

• 输入：$\mathbb{R}^2$上的二维格$\mathcal{L}$的一组基 $\mathbf{x},\mathbf{y}$，其中$\left|\mathbf{x}\right|<\left|\mathbf{y}\right|$
• 输出：格$\,\mathcal{L}\,$的一组最小基$\,\mathbf{v}_1,\mathbf{v}_2$
• 算法步骤：高斯算法伪代码

高斯算法中蕴含的思想与欧几里得算法类似，两者都是不断地实施先约化后交换的策略。在伪代码中，(2)(b)是约化步，(2)(c)(ii)是交换步。在约化步中会计算施密特正交化的系数，并且为了确保在格$\,\mathcal{L}\,$上运算，不能直接用施密特正交化系数，而是要将其取整后得到的$\,m\,$作为约化步中减去$\,\mathbf{v}_2\,$的系数。当$\, \left|\mathbf{v}_1\right|\le\left|\mathbf{v}_2\right|\,$时，算法结束并输出此时的${\, \mathbf{v}}_1\,$和${\ \mathbf{v}}_2\,$。可以证明算法输出的${\ \mathbf{v}}_1$和${\ \mathbf{v}}_2\,$是一组最小基，下面简述证明思路。

证明思路：首先，由取整的定义易知在算法的步骤(2)(b)执行后，有$\,\left|\mathbf{v}_2^\prime\cdot\mathbf{v}_1\right|\le\frac{1}{2}\left|\mathbf{v}_1\right|^2\,$，其中$\, \mathbf{v}_2^\prime\,$是步骤执行后所得新基的第二个向量。或者说，每次(2)(b)执行完毕后有 $\mu_{2,1} \le \frac{1}{2}$（此时称${\, \mathbf{v}}_1,{\ \mathbf{v}}_2\,$是 size-reduced的）。结合算法终止时$\, \left|\mathbf{v}_1\right|\le\left|\mathbf{v}_2\right|\,$这一条件即可证明$\, \left|\mathbf{v}_1\right| = \lambda_{1}(\mathcal{L}) \,$。这一点从几何上非常直观，读者不妨考虑一下$\, \left|\mathbf{v}_1\right| = \left|\mathbf{v}_2\right|\,$时的情形。接下来再证$\,\mathbf{v}_2\,$是与$\,\mathbf{v}_1\,$线性无关的最短向量即可（证这一步有点繁琐）。

上述证明思路来源于二维空间上的几何直观，后面会看到在高维格中无法用类似的思路证明。在高维空间中，长度（2-范数）就没那么符合直觉了。由此也能侧面理解，为什么SVP问题在低维格中是容易的，在高维格中是困难的。

纵观高斯算法的流程，其实就是在不停地让两个向量互相约化，直到它们无法变得更短为止。因此，高斯算法可以视为一种贪心算法，且可以推广至高维（见后面的推广高斯算法）。

算法实现

sagemath代码如下。

def Gauss(x,y):
    # step 1
    v1 = x; v2 = y
    finished = False
    # step 2
    while not finished:
        # (a)
        m = round(( v2.dot_product(v1) / v1.dot_product(v1) ))
        # (b)
        v2 = v2 - m*v1
        # (c)
        if v1.norm() <= v2.norm():
            finished = True
        else:
            v1, v2 = v2, v1
    
   return v1, v2

算法效能

高斯算法能够以平方级别的运行时间求解出一组Minkowski约化基（最小基），具体如下。

• 约化能力：设$\, \mathbf{x},\mathbf{y}\in\mathbb{R}^\mathbf{2}\,$是二维格$\,\mathcal{L}\,$的一组基，将$\mathbf{x},\mathbf{y}$作为高斯约化算法的输入，则算法一定能够在有限步内执行完成，且其输出的$\ \mathbf{v}_1,\mathbf{v}_2\,$是格$\,\mathcal{L}\,$的一组Minkowski约化基。
• 运行时间：输入二维格$\,\mathcal{L}\,$的任意一组基$\,\mathbf{u},\mathbf{v}\,$，假设$\, \left|\mathbf{u}\right|\le\left|\mathbf{v}\right|\,$，那么高斯算法会在$\, O\left(\log\left|\mathbf{v}\right|\cdot\left[1+\log\left|\mathbf{v}\right|-\log\lambda_1\left(\mathcal{L}\right)\right]\right)\,$的时间内运行完毕。

LLL算法

1982年诞生的LLL算法可视为高斯算法在高维格中的推广。接下来详细介绍原始LLL算法。

算法描述

设$\ \mathcal{L}\subset\mathbb{R}^m\,$是$\,n\,$维格，算法输入$\, \mathcal{L} \,$的任意一组基，并以多项式时间输出一组LLL约化基。首先介绍LLL约化基的概念。

LLL约化基：设$\, \mathbf{b}_1,\ldots,\mathbf{b}_n \,$是$\, \mathcal{L}\,$的一组格基，若其满足以下两个性质：

1. (size-reduce)：对于任意的$\, j<i\le n\,$，有$\, \left|\mu_{i,j}\right| \le \frac{1}{2}\,$，其中$\,\mu_{i,j}=\frac{\left\langle\mathbf{b}_i,\mathbf{b}_j^\ast\right\rangle}{\left\langle\mathbf{b}_j^\ast,\mathbf{b}_j^\ast\right\rangle}\,$为施密特正交化中的系数。
2. (Lovász condition)：对于任意的$\,\mathbf{b}_i,\ \mathbf{b}_{i+1}\,$有$\,\delta\left| \mathbf{b}_i^\ast \right|^2\le\left|\mathbf{b}_{i+1}^\ast+\mu_{i+1,i}\mathbf{b}_i^\ast \right|^2\,$.

则称$\, \mathbf{b}_1,\ldots,\mathbf{b}_n \,$是$\, \mathcal{L}\,$的一组$\delta-$LLL约化基。

性质2中的不等式$\,\delta\left| \mathbf{b}_i^\ast \right|^2\le\left|\mathbf{b}_{i+1}^\ast+\mu_{i+1,i}\mathbf{b}_i^\ast \right|^2\,$可以等价替换为$\, \left| \mathbf{b}_{i+1}^\ast \right|^2 \ge \left(\delta - \mu^{2}_{i+1,i} \right)\left| \mathbf{b}_{i}^\ast \right|^2 \ge \left(\delta - \frac{1}{4} \right)\left| \mathbf{b}_{i}^\ast \right|^2 \,$。性质1表明，LLL约化基中的向量是相对较短且近似正交的。性质2是为了根据范数对基中向量进行大致的排序。

下面给出LLL算法的伪代码：

原始LLL算法伪代码

简易实现

sagemath代码如下，参考 https://kel.bz/post/lll/

def max(a, b):
    return a if a > b else b

def LLL_v0(M, delta=0.75):
    B = deepcopy(M)
    Q, mu = B.gram_schmidt()
    n, k = B.nrows(), 1
    
    while k < n:
        
        # size reduction step
        for j in reversed(range(k)):
            if abs( mu[k][j] ) > 0.5:
                B[k] = B[k] - round( mu[k][j] ) * B[j]
                Q, mu = B.gram_schmidt()
        
        # swap step 
        if Q[k].dot_product(Q[k]) >= (delta - mu[k][k-1]^2) * Q[k-1].dot_product(Q[k-1]):
            k = k + 1
        else:
            B[k], B[k-1] = B[k-1], B[k]
            Q, mu = B.gram_schmidt()
            k = max(k-1,1)
    
    return B 

常规实现

在进行一次交换步或约化步之后，实际上只需要修改mu（施密特正交化系数）和Q（正交向量组）的个别值。而简易实现中，每次都会重新计算整个施密特正交化，这样的实现是低效的。

参考的伪代码不贴了，来源于 Lattice Basis Reduction - An Introduction to the LLL Algorithm and its Applications P.63

sagemath代码如下：

def LLL_v1(M, delta=0.75):

    if delta < 0.25:
        print("delta should be greater than 0.25. Choose delta = 0.75 now.")
    alpha = delta if 0.25 < delta < 1 else 0.75
    
    x = M
    n = M.nrows()
    
    def reduce(k, l):
        do_reduce = False
                   
        if abs(mu[k,l]) > 0.5:
            do_reduce = True
            
            y[k] = y[k] - mu[k,l].round() * y[l]
            for j in range(l):
                mu[k,j] -=  mu[k,l].round() * mu[l,j]
            mu[k,l] = mu[k,l] - mu[k,l].round()       

        return
    
    def exchange(k):
        
        y[k-1], y[k] = y[k], y[k-1]
        NU = mu[k,k-1]
        delta = gamma[k] + NU ^ 2 * gamma[k-1]
        mu[k,k-1] = NU * gamma[k-1] / delta    # all above is right
        gamma[k] = gamma[k] * gamma[k-1] / delta
        gamma[k-1] = delta

        for j in range(k-1):
            mu[k-1,j], mu[k,j] = mu[k,j], mu[k-1,j]
        for i in range(k+1, n):
            xi = mu[i,k]
            mu[i,k] = mu[i,k-1] - NU * mu[i,k]
            mu[i,k-1] = mu[k,k-1] * mu[i,k] + xi      
            
        return
    
    # step (1) 
    y = deepcopy(x)
    # step (2) 
    y_star, mu = y.gram_schmidt()
    gamma = [y_star[i].norm() ^ 2 for i in range(n)]
    
    # step (3)
    k = 1
    
    # step (4)
    while k < n:      
        # step (4)(a)    
        reduce(k, k-1)

        # step (4)(b)
        if gamma[k] >= (alpha - mu[k,k-1]^2) * gamma[k-1]:
            # (i)
            for l in reversed(range(k-1)):
                reduce(k, l)
            # (ii)
            k = k + 1
        else:
            # (iii)
            exchange(k)
            # (iv)
            if k > 1:
                k = k-1

    return y

注：这两个版本的算法输出会有所不同，但这并不是因为代码写的有错误。两个算法求出的结果都是一组LLL-约化基。

理论效能

在密码分析的使用中，一般会选取$\,\delta=0.99\,$或其他合适的值。我们最关心LLL求解SVP的能力，下面给出$\, \delta\,$取任意值时所得$\, \mathbf{b}_1\,$范数的上界。

约化能力：设$\, \mathbf{b}_1,\ldots,\mathbf{b}_n\,$是$\, n\,$维格$\, \mathcal{L}\,$的一组$\ \delta\,$- LLL约化基，则$\ \left| \mathbf{b}_1\right| \le\left(\frac{2}{\sqrt{4\delta-1}}\right)^{n-1}\lambda_1(\mathcal{L})\,$。

由定理可知，在LLL中$\, \delta\,$的选取会显著影响输出基的质量，$\, \delta\,$越大则基的范数越小。但算法中$\, \delta<1\ ,$，因此常见的选取为$\, \delta=0.99\,$。根据定理3.2.2，此时$\, \left|\mathbf{b}_1\right|<\left(1.35136\right)^\frac{n-1}{2}\lambda_1(\mathcal{L})\,$。

实际上，LLL算法输出基的质量在实践中一般优于上述定理给出的上界，以此估算LLL的实际表现是悲观的。与此相似，下面给出的时间复杂度上界也是一个悲观估计。

时间复杂度：设$\, \mathcal{L}\subset\mathbb{R}^m\,$为$\, n\,$维格，LLL算法输入基为$\, \mathbf{b}_1,\ldots,\mathbf{b}_n\,$，则LLL算法会在$\ O\left(n^6\ln^3\!{B}\right)\,$的时间内运行完毕。其中$\ \forall1\le i\le n\ ,\ \left|\mathbf{b}_i\right|<B\ .$

LLL算法的理论效能总结如下：算法能够在$\ O\left(n^6\ln^3{B}\right)\,$的时间内，输出质量较高的约化基。当算法中的参数选取为$\, \delta=0.99\,$时，输出基中第一个向量的欧氏范数满足$\, \left|\mathbf{b}_1\right|<\left(1.352\right)^\frac{n-1}{2}\lambda_1(\mathcal{L})\,$。再次强调，这些结论仅仅是算法性能的下限，直接用这些值来预测算法性能过于悲观。后面还会看到，改进LLL算法的时间复杂度明显优于这个上界。

BKZ算法

1994年，Schnorr等人提出了BKZ算法。该算法比LLL算法的约化能力更强，可视为LLL算法的一种改进，其中使用了KZ约化(Korkin-Zolotarev reduction)和深插法(deep insertion)。下面介绍原始BKZ算法，而目前使用的BKZ 2.0在后面介绍。

算法描述

KZ约化：KZ约化基是一组size-reduced，且其正交化后的向量范数为逐次最小长度的格基（特别地，基中第一个向量的长度即为$\,\lambda_1\,$）。计算高维格的KZ约化基是不切实际的，因为这需要要在输入格的投影子格上对SVP求解算法进行迭代式调用，其时间复杂度一般为超指数级。

为了以合理的时间代价得到比LLL约化基质量更好的基，Schnorr等人提出让格基的每个分块为KZ约化基即可。并且在原始BKZ中，分块的大小一般只会选取为10~30左右。下面给出BKZ约化基的概念。

BKZ约化：若$\, {\mathbf{b}}_1,\ldots,\mathbf{b}_n\,$为格$\,\mathcal{L}\,$的LLL约化基，且对于任意的$\,i\,$，有

$\ \left\|\mathbf{b}_i^\ast\right\|=\lambda_1\left(\mathcal{L}_{\left[i,min{\left(i+\beta-1,n\right)}\right]}\right)\$，

则称${\ \mathbf{b}}_1,\ldots,\mathbf{b}_n\,$为格$\,\mathcal{L}\,$的一组$\,\beta-$BKZ约化基，称其中的$\, \beta\,$为BKZ的分块大小。
在BKZ算法中，只需在分块投影子格$\, \mathcal{L}([\pi_i(\mathbf{b}_i),\pi_i(\mathbf{b}_{i+1}),\ldots,\pi_i(\mathbf{b}_{min\left(i+\beta-1,n\right)})]) \,$上求解SVP，这要比KZ约化容易得多。BKZ中这个求解SVP的子算法称为SVP oracle，一般使用格枚举(lattice enumeration)实现。

原始的BKZ使用精确格枚举算法，这个算法一定能够在输入投影子格上求解出SVP，但它的时间开销很大。实用的BKZ使用的是剪枝枚举算法，这种算法只能以一定的概率求解SVP，但它的时间开销比前者小很多。

枚举算法可视为对枚举树的DFS，剪枝枚举则是剪枝DFS。

原始BKZ伪代码如下。
输入：格$\,\mathcal{L}\,$的基$\ B={(\mathbf{b}}_1,\ldots,\mathbf{b}_n)\,$，分块大小$\, \beta\in\left\{2,\ldots,n\right\}\,$，施密特系数矩阵$\, \mu\,$和${\, \left|\mathbf{b}_1^\ast\right|}^2,\ldots,\left|\mathbf{b}_n^\ast\right|^2 \,$
输出：$\,\beta-$BKZ约化基$\, {(\mathbf{b}}_1,\ldots,\mathbf{b}_n)\,$

算法步骤：

原始BKZ算法伪代码

BKZ算法的大致流程如下：

先对输入基进行LLL作为预处理，之后对当前分块进行格枚举求解SVP。若枚举算法得到的最短向量不是当前分块的第一个向量，就将最短向量插入到分块前，重新对整个基进行LLL约化。直到对所有分块都操作完毕。这样得到的输出基通常会优于LLL约化基。分块大致可以视为一种滑动窗口，第一个分块是$(\mathbf{b}_1,\ldots,\mathbf{b}_{\beta})$，第二个分块是$(\mathbf{b}_2,\ldots,\mathbf{b}_{\beta + 1})$…总之每次窗口向右移动一个向量。注意最后的$\,\beta-2\,$个分块长度是小于$\,\beta \,$的。

为什么每次插入后要进行LLL呢？这主要是因为插入的子格最短向量与该子格的基线性相关，因此插入后当前的向量组就不是一组基了。而LLL能够消去线性相关性，同时进行一步约化。

理论效能

Hanrot等人运用动力系统分析出BKZ的约化能力下界为$\, \left|\mathbf{b}_1\right|\le\beta^{\frac{n-1}{2\left(\beta-1\right)}+\frac{3}{2}} \det(B)^\frac{1}{n}\,$。另一方面，当$\, \beta\,$设置为输入格维度$\, n\,$时，由BKZ约化基的定义可知$\, \left|\mathbf{b}_1\right|=\left|\mathbf{b}_1^\ast\right|=\lambda_1\left(\mathcal{L}\right)\,$。此时若BKZ算法能够终止，则其能够成功地求解$\, \mathcal{L}\,$上的SVP问题。
尽管在实践中BKZ算法较为有效，但它至今仍没有被证明是多项式时间的算法。2008年，Gama和Nyugen在文指出当时BKZ时间复杂度的理论上界为$\,O\left(n\beta\right)^n\,$，关于维度$\, n\,$为超指数级（当然这也是悲观上界）。他们对BKZ进行了大量的实验。实验结果表明原始BKZ运行时间关于维度$\, n\,$似乎是指数级而不是多项式级。BKZ 2.0论文中指出，原始BKZ算法中$\,\beta=20\,$较为实用，但$\,\beta\geq25\,$时运行时间会显著增加。输入高维格时，选取分块大小为$\, \beta\geq40\,$会使BKZ运行得非常慢，甚至可能跑不出结果。

总结与启发

前面总结了原始格基规约算法，其中高斯算法在理论上被研究的很透彻，而LLL和BKZ的理论效能分析结论并不实用，只是算法的下限。

目前使用的改进LLL算法与改进BKZ算法已经比原始算法的效能好很多，因此在实战中不使用两种原始算法。但即便如此原始算法仍然是值得回顾的，很容易受到如下启发：

1. 理解各算法的优化方向。对于LLL算法，其改进版的优化主要集中在于大数运算的优化（包括大数算法的改进和浮点数的正确使用），以及使用深插法(deep insertion)提升算法的约化能力；对于BKZ算法，其改进版的优化会集中在SVP oracle（枚举）的调用次数和SVP oracle算法本身的改进，减少运行时间从而能使用更大的$\,\beta\,$。
2. 算法效能很难用理论进行分析。事实上，大多数使用的改进后的算法在理论分析上也很困难，结论也不太理想，并且经典的分析方法不再适用。目前比较有效的理论分析一般是利用启发公式的方法进行启发式估计，设计模拟算法进行实验来得到启发式时间复杂度，许多分析还使用离散动力系统理论作为数学工具。
3. 在大多数场景下BKZ往往比LLL更实用，因为BKZ约化能力更强。回顾时，我们发现原始BKZ在大多数场景更加实用。只有对求解速度有较大要求或需要在高维格中循环调用算法时才会调用LLL，其他情况下BKZ才是更好的选择。

改进格基约化算法

目前，sagemath中的格基规约算法默认采用fpLLL的实现。在fpLLL中默认的LLL算法依照 $\mathrm{L}^2$算法实现，并结合H-LLL；默认的BKZ算法主要依照BKZ 2.0实现。对于LLL和BKZ，下面仅简单总结了$\, \mathrm{L}^2\,$算法和BKZ 2.0算法。

$\mathrm{L}^{2}$算法

该算法为一种浮点型LLL算法，其中采用了浮点数和大数运算算法来优化运行时间，并使用deep insertion来提升算法的约化能力。即便不使用大数运算优化，$\, \mathrm{L}^2$算法的理论时间复杂度也为$\, O\!\left(d^4(d+\log B)\,m \log B\right)\,$，远优于原始LLL。（$\,d\,$是格的维度，$\,B\,$是输入基中最长向量的范数，$\,\mathcal{L} \subset \mathbb{R}^{m}$）

BKZ 2.0

该算法为目前sagemath默认调用的BKZ算法，对原始BKZ算法进行了四个优化：

1. 将极限剪枝枚举算法(extreme pruning)和一种高概率线性剪枝算法(linear pruning)这两种算法搭配起来，作为BKZ 2.0的SVP oracle（论文中称为sound pruning）。这比最早提出的Schnorr-Euchner剪枝枚举算法还要快很多 。

   一次极限剪枝算法的成功概率虽低，但是速度非常快，以至于我们可以通过多次地调用它（例如一百次…），达到一个与其他算法相同的成功概率，速度却能快很多倍。

2. 以大量实验结果为依据，使用Gaussian Heuristic启发式对剪枝枚举半径的值进行初始化。具体来说，枚举半径的初始值是1.05GH与输入格基的第一个向量范数中最小的那个。

3. 使用早期中止技术，合理设置oracle的调用次数（多项式级别）。
4. 对局部基进行预处理。

BKZ 2.0的这些优化手段旨在降低BKZ的SVP oracle调用次数以及SVP oracle自身的运行时间。这一系列的优化使得BKZ 2.0可以使用较大的 $\, \beta\,$，从而使得其约化能力显著强于LLL。BKZ 2.0论文中指出，设定算法参数为$\,\beta \ge 90\,$，甚至$\,\beta = 110\,$都是可以的。

要想更深入的理解BKZ 2.0，就要学习一下格枚举算法。可以在某英文网站上看一下视频 Lattice-based cryptography II - Enumeration attacks 和 Random Sampling Revisited Lattice Enumeration with Discrete Pruning的前半部分。

BKZ 2.0论文是我的外文翻译，不过感觉这篇论文翻译难度较大，我的翻译还需完善一下。如果有人想看的话，可能会在2022年1月完善后放出。

扩展阅读

2004年高斯算法被Nguyen等人推广至高维，他们指出推广算法在4维格中输出基为欧氏范数为Minkowski约化基（最小基）。同时，在4维格中算法复杂度（就输入基中最长向量范数的比特长度$\,n\,$而言）至少是平方级，若使用快速大数运算方法，算法的时间复杂度有希望提升到$\,O\!\left(n\log{n}\right)\,$级别。论文：Low-Dimensional Lattice Basis Reduction Revisited

下面提及的算法在fpLLL中也有实现。

H-LLL以$\,\mathrm{L}^2$算法为基础，在计算施密特正交化（QR分解）时使用householder算法替换了 Cholesky算法从而加快了运行速度。（具体做法并没这么简单，为了防止精度损失导致结果与原来不同，整个算法被重组）。论文：H-LLL: Using Householder Inside LLL

2008年，Gama和Nyugen提出了slide reduction。算法结构很漂亮，并且它的理论效能强于使用中止技术的BKZ。不过最初的slide reduction算法，其实际表现远不如BKZ 2.0算法。论文：Finding Short Lattice Vectors within Mordell’s Inequality

2016年， Micciancio和Walter获得了很大成果。他们提出一种在对偶格上枚举最短向量的方法，并且这种方法不需要计算对偶基。这使得他们能够在slide reduction使用很大的block size。改进后的slide reduction，其效能与BKZ 2.0几乎差不多。并且更重要的是，在block size的值适中时，其理论效能与实际效能几乎一致。这意味着无需进行实验就可以估计格基约化算法对格密码的冲击。此外，他们还提出一种SDBKZ(self dual BKZ，即自对偶BKZ)，其实际效能与BKZ 2.0相差无几，但其理论效能很容易分析。总之，这篇论文对于想进一步了解格基规约算法的人来说非常值得阅读。论文：Practical, Predictable Lattice Basis Reduction

此外也推荐这些博客，与上面的内容相关：

• Lattice Blog Reduction – Part I: BKZ | Calvin Café: The Simons Institute Blog

• Lattice Blog Reduction – Part II: Slide Reduction | Calvin Café: The Simons Institute Blog

• Lattice Blog Reduction – Part III: Self-Dual BKZ | Calvin Café: The Simons Institute Blog

目前最强的算法是基于G6K的BKZ（全称General Sieve Kernel，读作Jessica），可以在英文网站上查找相关的讲解视频。论文：The General Sieve Kernel and New Records in Lattice Reduction

参考资料

文献

为了保证阅读体验，我没有在正文标注引用。本人只是把这方面内容重新组织和总结了一下，又写了一点自己的理解。根据以下论文的名字不难找到本文内容的出处。

1. Hoffstein J , Pipher J C , Silverman J H . An Introduction to Mathematical Cryptography. 2008.

2. Galbraith S D . Mathematics of Public Key Cryptography: Lattices. 2012.

3. Nguyen P Q , D Stehlé. Low-Dimensional Lattice Basis Reduction Revisited. 2009.

4. Lenstra A . Factoring polynomial with rational coefficients. 1982.

5. Bremner M R . Lattice Basis Reduction: An Introduction to the LLL Algorithm and Its Applications. 2011.

6. Schnorr C P, Euchner M. Lattice basis reduction: improved practical algorithms and solving subset sum problems. 1994.

7. Gama, Nicolas, et al. “Lattice Enumeration Using Extreme Pruning.” EUROCRYPT’10 Proceedings of the 29th Annual International Conference on Theory and Applications of Cryptographic Techniques, 2010, pp. 257–278.

8. Chen Y, Nguyen P Q. BKZ 2.0: Better lattice security estimates. 2011.

9. PQ Nguyen, D Stehlé. Floating-Point LLL Revisited. 2005.

10. 郑永辉,刘永杰,栾鸾.格基约化算法及其在密码分析中的应用综述. 2020.

11. Regev L O , Kaplan S E . Lattices in Computer Science LLL Algorithm. 2013.

12. Cohen H . A Course in Computational Algebraic Number Theory. 2013.

13. Hanrot G, Pujol X, Stehlé. Analyzing blockwise lattice algorithms using dynamical systems. 2011.

14. Gama N, Nguyen P Q. Predicting lattice reduction. 2008.

15. Morel I, Stehlé D, Villard G. H-LLL: using householder inside LLL. 2009.

博客

Building Lattice Reduction (LLL) Intuition | kel.bz

Lattice Blog Reduction – Part I: BKZ | Calvin Café: The Simons Institute Blog

Lattice Blog Reduction – Part II: Slide Reduction | Calvin Café: The Simons Institute Blog

Lattice Blog Reduction – Part III: Self-Dual BKZ | Calvin Café: The Simons Institute Blog

Lattice Blog Reduction – Part III: Self-Dual BKZ | Calvin Café: The Simons Institute Blog

还有一些英文视频，因为一些你懂得的原因这里就不贴了。