lll-low-dimension-attack.ipynb

Kernel: SageMath 10.0

Break: LLL Attack on Low-Dimension Lattice Scheme

Module 08 | Breaking Weak Parameters

When the lattice dimension is too small, the LLL algorithm tears through your encryption like tissue paper.

Why This Matters

Lattice-based cryptography relies on the hardness of finding short vectors in high-dimensional lattices. The LLL algorithm (notebook 08c) finds approximately short vectors in polynomial time, but its approximation factor degrades exponentially with dimension:

$$\|\mathbf{b}_1\| \le 2^{(n-1)/2} \cdot \lambda_1(L)$$

In low dimensions ($n \le 40$), LLL often finds vectors much shorter than this worst-case bound --- sometimes close to the actual shortest vector. This means any lattice-based scheme using small dimensions is completely broken by a polynomial-time algorithm.

In this notebook, we set up a toy LWE-based encryption scheme, break it with LLL when the dimension is small, and observe how increasing the dimension makes the attack fail.

The Scenario: A Toy LWE Encryption Scheme

We build a simplified LWE-based encryption scheme with deliberately small parameters. The setup follows notebook 08d:

• Key generation: Pick a random matrix $A \in \mathbb{Z}_q^{m \times n}$ and a secret vector $\mathbf{s} \in \mathbb{Z}_q^n$ with small entries. Compute $\mathbf{b} = A\mathbf{s} + \mathbf{e} \pmod{q}$ where $\mathbf{e}$ is a small error vector. The public key is $(A, \mathbf{b})$; the secret key is $\mathbf{s}$.

• Attack goal: Given the public key $(A, \mathbf{b})$, recover $\mathbf{s}$.

Recovering $\mathbf{s}$ from $(A, \mathbf{b})$ is equivalent to solving a Closest Vector Problem (CVP) on the $q$-ary lattice $\Lambda_q(A)$ --- find the lattice point $A\mathbf{s}$ that is closest to $\mathbf{b}$. If the dimension $n$ is small enough, LLL + Babai's algorithm solves this instantly.

# === Step 1: Define the toy LWE scheme ===
from sage.stats.distributions.discrete_gaussian_integer import DiscreteGaussianDistributionIntegerSampler

def lwe_keygen(n, m, q, sigma):
    """
    Generate an LWE key pair.
    Returns: (A, b, s, e) where public key = (A, b), secret key = s.
    """
    Zq = Zmod(q)
    D = DiscreteGaussianDistributionIntegerSampler(sigma=float(sigma))
    
    s = vector(Zq, [D() for _ in range(n)])   # small secret
    A = random_matrix(Zq, m, n)                # random public matrix
    e = vector(Zq, [D() for _ in range(m)])    # small error
    b = A * s + e                               # public vector
    
    return A, b, s, e

# Small parameters: dimension 10, easily breakable
n = 10
m = 20
q = 101
sigma = 3.0

set_random_seed(42)
A, b, s_secret, e_secret = lwe_keygen(n, m, q, sigma)

print(f'LWE parameters: n={n}, m={m}, q={q}, sigma={sigma}')
print(f'Secret vector s = {s_secret}')
print(f'Error vector e  = {e_secret}')
print(f'\nPublic key: matrix A ({m}x{n}) and vector b ({m} entries)')
print(f'Attacker sees (A, b) and must recover s.')

Step 2: Construct the Lattice

To attack LWE with lattice reduction, we embed the problem into a lattice. The $q$-ary lattice associated with $A$ is:

$$\Lambda_q(A) = \{\mathbf{y} \in \mathbb{Z}^m : \mathbf{y} \equiv A\mathbf{s} \pmod{q} \text{ for some } \mathbf{s}\}$$

We construct a lattice basis by stacking $A^T$ on top of $qI_m$. The target vector $\mathbf{b}$ is close to the lattice point $A\mathbf{s} \bmod q$ (displaced by the small error $\mathbf{e}$). So recovering $\mathbf{s}$ reduces to CVP.

# === Step 2: Build the q-ary lattice ===

def build_q_ary_lattice(A, q):
    """
    Build the basis for the q-ary lattice Lambda_q(A).
    Rows of [A^T; q*I_m] generate the lattice.
    """
    n = A.ncols()
    m = A.nrows()
    A_int = matrix(ZZ, A)  # lift to integers
    basis = block_matrix([
        [A_int.transpose()],          # n x m
        [q * identity_matrix(ZZ, m)]  # m x m
    ])  # (n + m) x m
    return basis

L_basis = build_q_ary_lattice(A, q)
print(f'Lattice basis dimensions: {L_basis.nrows()} x {L_basis.ncols()}')
print(f'  (n + m) = {n} + {m} = {n + m} rows generating vectors in Z^{m}')
print(f'\nThe target vector b is close to a lattice point.')
print(f'The error (distance to closest point) has norm ~= sigma * sqrt(m) = {sigma * sqrt(m):.2f}')

Step 3: Apply LLL + Babai to Recover the Secret

Our attack has two phases:

1. LLL reduction: Apply .LLL() to the lattice basis to get a reduced basis with short, nearly orthogonal vectors.

2. Babai's nearest plane algorithm: Use the reduced basis to find the lattice point closest to $\mathbf{b}$. If the reduced basis is good enough, Babai's algorithm finds $A\mathbf{s} \bmod q$, from which we recover $\mathbf{s}$.

# === Step 3: LLL reduction + Babai's nearest plane ===

def babai_cvp(basis, target):
    """
    Babai's nearest plane algorithm for approximate CVP.
    Given an LLL-reduced basis and a target vector, find the
    closest lattice vector.
    """
    B = basis.change_ring(QQ)
    t = vector(QQ, target)
    G, _ = B.gram_schmidt()
    b = t
    for i in range(B.nrows() - 1, -1, -1):
        c = (b * G[i]) / (G[i] * G[i])
        b = b - round(c) * B[i]
    return target - b  # closest lattice vector

def to_signed(x, q):
    """Convert x in Z_q to signed representation in (-q/2, q/2]."""
    x = ZZ(x) % q
    return x if x <= q // 2 else x - q

# Phase 1: LLL-reduce the lattice basis
t0 = walltime()
L_reduced = L_basis.LLL()
lll_time = walltime() - t0

# Phase 2: Babai's algorithm to find the closest lattice point to b
b_int = vector(ZZ, b)
closest = babai_cvp(L_reduced, b_int)

# The closest lattice point should be A*s (mod q)
closest_mod_q = vector(Zmod(q), [ZZ(x) % q for x in closest])
As_actual = A * s_secret

print(f'LLL reduction completed in {lll_time:.3f} seconds')
print(f'\nClosest lattice point (mod q): {closest_mod_q}')
print(f'True A*s (mod q):              {As_actual}')
print(f'Match: {closest_mod_q == As_actual}')

# === Step 4: Recover the secret vector s from the closest lattice point ===

# Now we know A*s mod q. Solve A*x = closest (mod q) for x.
# Use the first n rows of A (assuming they form an invertible submatrix).

Zq = Zmod(q)
A_square = matrix(Zq, A[:n])
target_square = vector(Zq, closest_mod_q[:n])

try:
    s_recovered = A_square.solve_right(target_square)
    print(f'Recovered secret: s = {s_recovered}')
    print(f'Actual secret:    s = {s_secret}')
    print(f'\nSecret recovered correctly: {s_recovered == s_secret}')
    print(f'\n*** SCHEME BROKEN! The low dimension ({n}) made LLL+Babai sufficient. ***')
except Exception as ex:
    print(f'Could not solve directly: {ex}')
    print('Trying alternative recovery...')

Step 5: Increasing Dimension Makes LLL Fail

Now we repeat the attack for increasing dimensions. As $n$ grows:

• The lattice dimension grows (making LLL slower and less effective)

• The error is harder to strip away (LLL's approximation degrades exponentially)

• At some point, LLL + Babai can no longer find the closest lattice point

This is exactly the security mechanism of real-world lattice-based crypto.

# === Step 5: Attack success vs. dimension ===

dimensions = [6, 8, 10, 14, 18, 24, 30, 40, 50]
results = []

print('n m q sigma Attack success? Time (s)')
for n_test in dimensions:
    m_test = 2 * n_test
    q_test = next_prime(max(101, n_test^2))
    sigma_test = max(2.0, float(sqrt(n_test)))
    
    set_random_seed(100 + n_test)  # reproducible per dimension
    A_t, b_t, s_t, e_t = lwe_keygen(n_test, m_test, q_test, sigma_test)
    
    t0 = walltime()
    try:
        basis_t = build_q_ary_lattice(A_t, q_test)
        L_red_t = basis_t.LLL()
        closest_t = babai_cvp(L_red_t, vector(ZZ, b_t))
        closest_mod = vector(Zmod(q_test), [ZZ(x) % q_test for x in closest_t])
        As_true = A_t * s_t
        success = (closest_mod == As_true)
    except Exception:
        success = False
    elapsed = walltime() - t0
    
    results.append((n_test, success, elapsed))
    print(f'{n_test} {m_test} {q_test} {sigma_test:>6.1f} {str(success)} {elapsed:>10.3f}')

print(f'\nAs dimension increases, the LLL attack stops working.')
print(f'The transition happens around n ~ 20-40 for these parameters.')

The Fix: Use Real-World Dimensions

Modern lattice-based schemes use parameters far beyond LLL's reach:

Scheme	Ring dimension $n$	Module rank $k$	Effective lattice dim	Security
ML-KEM-512 (Kyber)	256	2	~512	AES-128 equivalent
ML-KEM-768 (Kyber)	256	3	~768	AES-192 equivalent
ML-KEM-1024 (Kyber)	256	4	~1024	AES-256 equivalent

At dimension 512+, even the most advanced lattice reduction algorithms (BKZ-2.0, G6K sieve) cannot find short enough vectors to break the scheme. The best known attacks require time $2^{O(n)}$, which for $n = 512$ is astronomically large.

The appropriate noise level $\sigma$ is chosen so that:

1. The error is large enough that lattice reduction cannot strip it away

2. The error is small enough that legitimate decryption still works (the noise does not overwhelm the message)

For Kyber, the error uses a centered binomial distribution with small parameter $\eta$, giving coefficients in $\{-\eta, \ldots, \eta\}$.

# === Exercise: Plot LLL success rate vs. dimension ===
#
# For each dimension n in [6, 8, 10, 12, 14, 16, 18, 20, 25, 30],
# run 10 trials of the LLL attack and record the success rate.

test_dims = [6, 8, 10, 12, 14, 16, 18, 20, 25, 30]
num_trials = 10
success_rates = []

for n_exp in test_dims:
    m_exp = 2 * n_exp
    q_exp = next_prime(max(101, n_exp^2))
    sigma_exp = max(2.0, float(sqrt(n_exp)))
    
    wins = 0
    for trial in range(num_trials):
        try:
            A_e, b_e, s_e, e_e = lwe_keygen(n_exp, m_exp, q_exp, sigma_exp)
            basis_e = build_q_ary_lattice(A_e, q_exp)
            L_red_e = basis_e.LLL()
            closest_e = babai_cvp(L_red_e, vector(ZZ, b_e))
            closest_e_mod = vector(Zmod(q_exp), [ZZ(x) % q_exp for x in closest_e])
            if closest_e_mod == A_e * s_e:
                wins += 1
        except Exception:
            pass
    rate = wins / num_trials
    success_rates.append((n_exp, rate))
    print(f'n={n_exp}: success rate = {rate:.0%} ({wins}/{num_trials})')

# Plot
p = list_plot(success_rates, plotjoined=True, marker='o',
              color='red', thickness=2)
p.axes_labels(['Lattice dimension $n$', 'LLL attack success rate'])
show(p, figsize=(8, 5), title='LLL Attack Success vs. Dimension',
     ymin=-0.05, ymax=1.05)

Summary

Dimension	LLL Attack	Real-World Status
$n \le 15$	Instant break	Toy only
$n \approx 20{-}40$	Sometimes works	Still insecure
$n \ge 50$	Fails consistently	Marginal
$n \ge 256$ (Kyber)	No known attack	Standardized by NIST

Key takeaways:

• The LLL algorithm (from notebook 08c) combined with Babai's nearest plane algorithm can completely break LWE-based schemes when the dimension is small.

• The attack works by reducing CVP on the $q$-ary lattice $\Lambda_q(A)$ to a short vector problem, which LLL handles well in low dimensions.

• LLL's approximation factor degrades exponentially with dimension, so increasing $n$ makes the attack fail.

• Real-world schemes (ML-KEM / Kyber) use $n \ge 256$ with module structure, placing the effective lattice dimension at 512+ --- far beyond LLL's reach.

• The fix: use dimension $\ge 512$ and appropriate noise. Dimension is the primary security knob.

---

Back to Module 08: Lattices and Post-Quantum Cryptography