密码学基础之LLL算法

• LLL & GCD

• LLL & Gram-Schmidt

• LLL & Gaussian Lattice Reduction

• LLL

• A Deeper Dive into LLL

• 总结

LLL & GCD

LLL 算法和 GCD 算法其实并没有那么的像，不过从整体层面上来看它们有着相似的流程。首先我们看到 GCD 的伪代码

def euclid_gcd(a, b):
    if b == 0: # base case
        return a
    x = a mod b # reduction step
    return euclid_gcd(b, x) # swap step

def lll(basis):
    while k <= n:
        for j in reverse(range(k-1, 0)): # reduction step loop
            m = mu(k,j)
            basis[k] = basis[k] - mu*basis[j] # vector reduction
            # update orthogonalized basis
    if lovasz_condition:
        k += 1
    else:
        basis[k], basis[k+1] = basis[k+1], basis[k] # swap step
        # update orthogonalized basis
        k = max(k-1,1)
    return basis

LLL & Gram-Schmidt

LLL & Gaussian Lattice Reduction

def gauss_reduction(v1, v2):
    while True:
        if v2.norm() < v1.norm():
            v1, v2 = v2, v1 # swap step
        m = round( (v1 * v2) / (v1 * v1) )
        if m == 0:
            return (v1, v2)
        v2 = v2 - m*v1 # reduction step

LLL

A Deeper Dive into LLL

def LLL(B, delta):
    Q = gram_schmidt(B)

    def mu(i,j):
        v = B[i]
        u = Q[j]
        return (v*u) / (u*u)

    n, k = B.nrows(), 1
    while k < n:

        # length reduction step
        for j in reversed(range(k)):
            if abs(mu(k,j)) > .5:
                B[k] = B[k] - round(mu(k,j))*B[j]
                Q = gram_schmidt(B)

        # swap step
        if Q[k]*Q[k] >= (delta - mu(k,k-1)**2)*(Q[k-1]*Q[k-1]):
            k = k + 1
        else:
            B[k], B[k-1] = B[k-1], B[k]
            Q = gram_schmidt(B)
            k = max(k-1, 1)

   return B

我们从 mu 函数开始分析

mu

Length Reduction

我们关注代码中与长度缩减相关的部分

n, k = B.nrows(), 1
# outer loop condition
while k < n:
    # length reduction loop
    for j in reversed(range(k)):
        if abs(mu(k,j)) > .5:
            # reduce B[k]
            B[k] = B[k] - round(mu(k,j))*B[j]
            # re-calculate GS with new basis B
            Q = gram_schmidt(B)

B[0] = B[0]
B[1] = B[1] - round(mu(1, 0))*B[0]
B[2] = B[2] - round(mu(2, 1))*B[1] - round(mu(2, 0))*B[0]
...
B[k] = B[k] - round(mu(k, k-1))*B[k-1] - round(mu(k, k-2))*B[k-2] - ... - round(mu(k, 0))*B[0]

Q[0] = B[0]
Q[1] = B[1] - mu(1, 0)*Q[0]
Q[2] = B[2] - mu(2, 1)*Q[1] - mu(2, 0)*Q[0]
...
Q[k] = B[k] - mu(k, k-1)*Q[k-1] - mu(k, k-2)*Q[k-2] - ... - mu(k, 0)*Q[0]

The Lovász Condition and the Swap Step

再关注到代码中的交换部分

    # swap step
    if Q[k]*Q[k] >= (delta - mu(k,k-1)**2)*(Q[k-1]*Q[k-1]):
        k = k + 1
    else:
        B[k], B[k-1] = B[k-1], B[k]
        Q = gram_schmidt(B)
        k = max(k-1, 1)
return B

而格 的最短向量 ，根据Minkowski凸集定理有

总结