4.1 LLL Algorithm

The LLL algorithm, introduced by Arjen Lenstra, Hendrik Lenstra, and László Lovász in their 1982 paper Factoring polynomials with rational arithmetic, was the first polynomial-time algorithm for finding a provably short vector in an arbitrary lattice. Its primary motivation was factoring polynomials with rational coefficients, but it soon found applications in attacking knapsack cryptosystems, solving integer programs in fixed dimension, and Diophantine approximation. Before LLL, lattice reduction was an open problem. After LLL, it became the workhorse of lattice cryptanalysis — and remains so today.

What Does LLL Stand For?

LLL stands for Lenstra–Lenstra–Lovász, the surnames of its three inventors. The algorithm takes a long, nearly dependent lattice basis and returns a shorter, more orthogonal basis for the same lattice. It runs in polynomial time and gives an approximate short vector rather than solving exact SVP.

Gram–Schmidt Orthogonalization

LLL is built on the Gram–Schmidt orthogonalization of the basis. Given basis vectors $b_1, \dots, b_n$, define the Gram–Schmidt vectors $\tilde{b}_1, \dots, \tilde{b}_n$ by:

where the Gram–Schmidt coefficients are:

The Gram–Schmidt vectors are orthogonal but not in the lattice — they live in the real span. Their norms $\|\tilde{b}_i\|$ measure how much each basis vector contributes beyond the previous ones. A reduced basis has Gram–Schmidt vectors of roughly comparable length.

LLL Reduction Conditions

A basis $B = [b_1 \mid \cdots \mid b_n]$ is LLL-reduced with parameter $\delta \in (1/4, 1)$ if it satisfies two conditions:

Size reduction — all off-diagonal Gram–Schmidt coefficients are small:

Lovász condition — consecutive Gram–Schmidt vectors do not decrease too fast:

The standard choice is $\delta = 3/4$. When $\delta$ is closer to 1, the output is better but the algorithm takes more iterations. At $\delta = 1$ the algorithm is no longer known to run in polynomial time, and its output is still only an approximation — it does not solve SVP.

The Algorithm

LLL interleaves two operations: size-reduce each vector against all previous ones, then check the Lovász condition and swap adjacent vectors if it fails.

Input: basis $B = (b_1, \dots, b_n)$, parameter $\delta \in (1/4, 1)$
Output: LLL-reduced basis

1. Compute Gram–Schmidt orthogonalization of $B$.
2. Set $k = 2$.
3. Size-reduce $b_k$: for $j = k-1$ down to $1$, set $b_k \leftarrow b_k - \lfloor \mu_{k,j} \rceil\, b_j$ and update Gram–Schmidt.
4. If Lovász condition holds at $k$, increment $k \leftarrow k+1$.
5. Otherwise swap $b_{k-1}$ and $b_k$, update Gram–Schmidt, set $k \leftarrow \max(k-1, 2)$.
6. Repeat from step 3 until $k > n$.

Output Quality

The first vector $b_1$ of an LLL-reduced basis satisfies:

For $\delta = 3/4$ this gives an approximation factor of $2^{(n-1)/2}$. In practice LLL performs far better than this worst-case bound — experimentally the output is roughly $1.02^n \cdot \lambda_1$.

Complexity

LLL runs in polynomial time. For an $n$-dimensional lattice with basis vectors of bit-length at most $B$:

bit operations (with schoolbook integer arithmetic). The number of swap steps is bounded by $\mathcal{O}(n^2 B)$. This polynomial bound — compared to the exponential time needed for exact SVP — is what makes LLL practical: libraries such as fplll reduce bases with hundreds of dimensions on an ordinary laptop.

Cryptographic Impact

The original 1982 paper applied LLL to factoring polynomials with rational coefficients. Shamir broke the basic Merkle–Hellman knapsack cryptosystem the same year using Lenstra’s integer programming algorithm rather than LLL, but LLL soon became the standard knapsack-breaking tool: Lagarias and Odlyzko (1985) used it to solve low-density subset-sum instances by finding a short vector in a carefully constructed lattice.

LLL is a subroutine inside every stronger lattice reduction algorithm (BKZ, HKZ). It is also used in attacks on poorly parameterized RSA (Coppersmith’s method uses LLL to find small roots of polynomials), in breaking ECDSA when nonces are biased, and in solving the hidden number problem.

For lattice-based cryptography like Kyber and Dilithium, the parameters are chosen precisely so that LLL alone is far too weak — but it remains the essential building block of every known attack.

LLL Variants: Complexity Comparison

Several improved variants of LLL have been developed, trading implementation complexity for better practical performance. The table below summarizes the main variants by their theoretical complexity and practical approximation quality.

LLL ($\delta = 3/4$): original algorithm. Bit complexity $\mathcal{O}(n^6 B^3)$. Approximation factor $2^{(n-1)/2}$ worst case.

L² algorithm (Nguyen–Stehlé, 2005): floating-point LLL with rigorous error control. Runs in $\mathcal{O}(n^5 (n + B) B)$ bit operations — strictly better than classical LLL. Achieves the same output quality guarantee but is the standard in all modern implementations. The key insight is to use a fixed-precision floating-point arithmetic model with carefully chosen precision $\eta \geq n + \log_2 B$ bits, re-establishing exactness guarantees without symbolic arithmetic.

Deep insertions LLL (Schnorr–Euchner, 1994): instead of only swapping adjacent vectors, inserts $b_k$ at the earliest position where it would satisfy the Lovász condition. Produces better bases in practice, but with unrestricted deep insertions no polynomial worst-case running-time bound is known.

BKZ-β (Schnorr, 1987; Schnorr–Euchner, 1994): with block size $\beta = 2$, BKZ is essentially LLL (each 2-dimensional block is Lagrange-reduced). Block size is the parameter controlling the transition from polynomial (LLL) to exponential (BKZ) complexity.

Python Implementation from Scratch

The following is a complete, self-contained Python implementation of the LLL algorithm. It uses only NumPy and follows the mathematical description above step by step: Gram–Schmidt orthogonalization, size reduction, and the Lovász swap condition.

import numpy as np

def gram_schmidt(B):
    """
    Compute Gram-Schmidt orthogonalization.

    Returns:
        B_star: orthogonal vectors (same shape as B)
        mu: matrix of Gram-Schmidt coefficients
             mu[i,j] = <b_i, b*_j> / <b*_j, b*_j>
    """
    n = B.shape[0]
    B_star = np.zeros_like(B, dtype=float)
    mu = np.zeros((n, n), dtype=float)

    for i in range(n):
        B_star[i] = B[i].copy()
        for j in range(i):
            # project b_i onto each previous orthogonal vector b*_j
            mu[i, j] = np.dot(B[i], B_star[j]) / np.dot(B_star[j], B_star[j])
            B_star[i] -= mu[i, j] * B_star[j]

    return B_star, mu


def lll_reduction(B, delta=0.75):
    """
    LLL lattice basis reduction.

    Args:
        B: integer matrix where rows are basis vectors (n x m)
        delta: reduction parameter in (0.25, 1). Default 0.75.
               Higher delta → better output but more iterations.

    Returns:
        B: LLL-reduced basis (modified in place)
    """
    B = np.array(B, dtype=float)
    n = B.shape[0]
    B_star, mu = gram_schmidt(B)

    k = 1
    while k < n:
        # === Step 1: Size reduction ===
        # Make |mu[k,j]| <= 0.5 for all j < k
        # This ensures basis vectors are not too skewed
        for j in range(k - 1, -1, -1):
            if abs(mu[k, j]) > 0.5:
                # Subtract the nearest integer multiple of b_j from b_k
                q = round(mu[k, j])
                B[k] -= q * B[j]
                # Update Gram-Schmidt coefficients
                B_star, mu = gram_schmidt(B)

        # === Step 2: Lovász condition ===
        # Check: delta * ||b*_{k-1}||^2 <= ||b*_k||^2 + mu[k,k-1]^2 * ||b*_{k-1}||^2
        # This prevents Gram-Schmidt norms from dropping too fast
        norm_k = np.dot(B_star[k], B_star[k])
        norm_k1 = np.dot(B_star[k - 1], B_star[k - 1])
        lovasz = norm_k + mu[k, k - 1] ** 2 * norm_k1

        if lovasz >= delta * norm_k1:
            # Condition satisfied → move to next index
            k += 1
        else:
            # Condition violated → swap b_k and b_{k-1}
            B[[k, k - 1]] = B[[k - 1, k]]
            B_star, mu = gram_schmidt(B)
            # Step back (but not below index 1)
            k = max(k - 1, 1)

    return B


# === Example usage ===
# Create a "bad" 4-dimensional basis with nearly parallel vectors
basis = np.array([
    [1,  1,  1,  1],
    [-1, 0,  0,  0],
    [3,  5,  6,  6],
    [1,  2,  3,  7],
])

print("Original basis:")
print(basis)
print("Norms:", [round(np.linalg.norm(row), 2) for row in basis])

reduced = lll_reduction(basis, delta=0.75)
print("\nLLL-reduced basis:")
print(reduced.astype(int))
print("Norms:", [round(np.linalg.norm(row), 2) for row in reduced])

How this works step by step:

1. Gram–Schmidt orthogonalization decomposes each basis vector into a component orthogonal to all previous vectors ($\tilde{b}_i$) plus projections onto them ($\mu_{i,j}$ coefficients). The orthogonal components reveal the “true” contribution of each vector.

2. Size reduction ensures $|\mu_{k,j}| \leq 1/2$ by subtracting integer multiples of earlier basis vectors. This is the lattice analogue of reducing off-diagonal entries in row echelon form — except we round to the nearest integer to stay in the lattice.

3. The Lovász condition checks that consecutive Gram–Schmidt norms do not drop too sharply. When violated, the algorithm swaps the two vectors. This swap strictly decreases a potential function $\prod_i \|\tilde{b}_i\|^{2(n-i)}$, guaranteeing termination in polynomial time.

4. The index $k$ moves forward when the Lovász condition holds and steps back after a swap, ensuring no earlier violations are introduced.

Note: This implementation recomputes Gram–Schmidt from scratch after each update for clarity. Production implementations (like FPLLL) use incremental updates, which reduces the per-iteration cost from $\mathcal{O}(n^2)$ to $\mathcal{O}(n)$.

LLL in Practice: FPLLL

The standard implementation of LLL (and BKZ) is FPLLL (Floating-Point LLL), an open-source C++ library maintained by the lattice cryptography community. It implements the L² algorithm, BKZ 2.0 with pruned enumeration, and the g6k sieve interface.

A minimal FPLLL session in Python via the fpylll wrapper:

from fpylll import IntegerMatrix, LLL

# create a random 40-dimensional lattice basis
A = IntegerMatrix.random(40, "qary", k=20, bits=30)

# run LLL with delta = 0.99
LLL.reduction(A, delta=0.99)

# inspect first basis vector length
print(A[0].norm())

Typical input/output: a 100-dimensional basis with entries of ~100 bits. LLL reduces it in under one second on a modern CPU. The first vector of the output is typically around $1.02^{100}$ times the lattice minimum — roughly 7× the theoretical minimum, but far shorter than a random basis vector (which would be exponentially longer). For an $n$-dimensional lattice arising from an RSA modulus, this translates directly into small-root-finding capability via Coppersmith’s method.

Floating-point precision: the L² algorithm uses double precision ($\approx 53$ bits) for small dimensions and switches to arbitrary-precision arithmetic (via MPFR) when the basis coefficients grow large. FPLLL handles this transition automatically, controlled by the float_type parameter (“double”, “long double”, “dpe”, “mpfr”). For dimensions above ~170 or basis bitlength above ~500, double precision accumulates enough rounding error to produce incorrect Gram–Schmidt coefficients, and MPFR is required.