Break: LWE Secret Recovery Without Noise

Module 08 | Breaking Weak Parameters

Remove the noise from LWE and Gaussian elimination eats your secret for breakfast.

Why This Matters

The Learning With Errors problem (notebook 08d) is:

\mathbf{b} = A\mathbf{s} + \mathbf{e} \pmod{q}

The security of LWE --- and by extension ML-KEM (Kyber), ML-DSA (Dilithium), and every lattice-based scheme built on it --- comes entirely from the error term $\mathbf{e}$ .

Without noise, $\mathbf{b} = A\mathbf{s} \pmod{q}$ is just a system of linear equations over $\mathbb{Z}_q$ . Gaussian elimination solves it in $O(n^3)$ .

In this notebook, we demonstrate this concretely: first we break noiseless "LWE" instantly, then we gradually add noise and watch the attack degrade from perfect recovery to total failure.

The Scenario: "LWE" Without Noise

An implementer decides that the error distribution is "just overhead" and sets $\mathbf{e} = \mathbf{0}$ . After all, the random matrix $A$ should provide enough "mixing" to hide $\mathbf{s}$ , right?

Let's find out.

In [ ]:

# === Step 1: Generate a noiseless LWE instance ===

n = 8       # dimension
m = 12      # number of equations (more than n for overdetermined system)
q = 251     # prime modulus

Zq = Zmod(q)
set_random_seed(42)

# Secret vector (could be any vector in Z_q^n)
s_secret = random_vector(Zq, n)

# Random public matrix
A = random_matrix(Zq, m, n)

# "LWE" with ZERO noise
e_zero = zero_vector(Zq, m)
b_noiseless = A * s_secret + e_zero  # = A * s, no noise at all

print(f'Parameters: n={n}, m={m}, q={q}')
print(f'Secret:  s = {s_secret}')
print(f'Error:   e = {e_zero}  (ALL ZEROS!)')
print(f'\nPublic:  A is a {m}x{n} matrix over Z_{q}')
print(f'Public:  b = A*s = {b_noiseless}')
print(f'\nThe attacker sees (A, b) and wants to find s.')

In [ ]:

# === Step 2: Break it with Gaussian elimination ===

# Use the first n rows to form a square system A[:n] * x = b[:n]
A_square = matrix(Zq, A[:n])
b_square = b_noiseless[:n]

# Solve: this is just linear algebra
s_recovered = A_square.solve_right(b_square)

print('=== Gaussian Elimination Attack ===')
print(f'Recovered: s = {s_recovered}')
print(f'Actual:    s = {s_secret}')
print(f'Match: {s_recovered == s_secret}')
print(f'\n*** SECRET RECOVERED INSTANTLY! ***')
print(f'Without noise, LWE is just a linear system.')
print(f'Gaussian elimination costs O(n^3) = O({n}^3) = O({n^3}) operations.')

In [ ]:

# === Step 3: Verify on ALL m equations, not just the first n ===

# The recovered s must satisfy ALL m equations, not just the first n
b_check = A * s_recovered

print('Verification: does b = A * s_recovered for ALL m equations?')
print(f'  A * s_recovered = {b_check}')
print(f'  b (public)      = {b_noiseless}')
print(f'  All match: {b_check == b_noiseless}')
print(f'\nWith zero noise, the system is perfectly consistent.')
print(f'Every equation confirms the same secret.')

Step 4: Gradually Add Noise

Now we add increasing amounts of noise and observe the transition:

Zero noise: Gaussian elimination recovers $\mathbf{s}$ perfectly.
Tiny noise: Rounding tricks might still recover $\mathbf{s}$ .
Moderate noise: Gaussian elimination produces garbage.
Proper noise ( $\sigma \ge \sqrt{n}$ ): No known efficient attack.

The key quantity is the ratio $\sigma / q$ . When $\sigma / q$ is negligible, the noise barely perturbs the linear system. When $\sigma / q$ is significant, the noise completely masks the algebraic structure.

In [ ]:

# === Step 4: Noise level vs. Gaussian elimination success ===

from sage.stats.distributions.discrete_gaussian_integer import DiscreteGaussianDistributionIntegerSampler

sigma_values = [0.0, 0.5, 1.0, 1.5, 2.0, 3.0, 5.0, 8.0, 12.0, 20.0]
num_trials = 50
results = []

print(f'Testing Gaussian elimination on LWE with increasing noise')
print(f'Parameters: n={n}, m={m}, q={q}, {num_trials} trials per sigma')
print(' sigma sigma/q Recovery rate')
for sig in sigma_values:
    successes = 0
    for _ in range(num_trials):
        s_trial = random_vector(Zq, n)
        A_trial = random_matrix(Zq, m, n)
        
        if sig == 0:
            e_trial = zero_vector(Zq, m)
        else:
            D = DiscreteGaussianDistributionIntegerSampler(sigma=float(sig))
            e_trial = vector(Zq, [D() for _ in range(m)])
        
        b_trial = A_trial * s_trial + e_trial
        
        # Attack: Gaussian elimination
        try:
            s_guess = A_trial[:n].solve_right(b_trial[:n])
            if s_guess == s_trial:
                successes += 1
        except Exception:
            pass
    
    rate = successes / num_trials
    results.append((sig, rate))
    print(f' {sig:>8.1f} {sig/q:>8.4f} {rate:>14.0%}')

print(f'\nEven tiny noise (sigma=1) severely degrades Gaussian elimination.')

In [ ]:

# === Plot: Recovery success vs noise magnitude ===

p = list_plot(results, plotjoined=True, marker='o',
              color='steelblue', thickness=2)
p.axes_labels(['Noise standard deviation $\\sigma$',
               'Secret recovery success rate'])
show(p, figsize=(8, 5),
     title=f'Gaussian Elimination vs. LWE Noise (n={n}, q={q})',
     ymin=-0.05, ymax=1.05)

Why Does Even Tiny Noise Kill Gaussian Elimination?

Gaussian elimination is an exact procedure. It solves $A\mathbf{x} = \mathbf{b}$ by row-reducing the augmented matrix $[A | \mathbf{b}]$ . When the true system is $A\mathbf{s} + \mathbf{e} = \mathbf{b}$ , Gaussian elimination "sees" the system $A\mathbf{x} = \mathbf{b}$ and finds some $\hat{\mathbf{x}}$ satisfying the first $n$ equations exactly.

But $\hat{\mathbf{x}} \ne \mathbf{s}$ because the noise $\mathbf{e}$ corrupts the right-hand side. The key insight: in modular arithmetic, there is no notion of "approximately correct." A solution is either exactly right or completely wrong. Even a single unit of error in one equation propagates through back-substitution and corrupts the entire solution.

This is fundamentally different from floating-point linear algebra, where small perturbations cause small changes in the solution. Over $\mathbb{Z}_q$ , small perturbations cause random changes in the solution.

In [ ]:

# === Demonstrate: what Gaussian elimination returns when noise is present ===

def to_signed(x, q):
    x = ZZ(x) % q
    return x if x <= q // 2 else x - q

# One LWE instance with moderate noise
set_random_seed(7)
sigma_demo = 3.0
D_demo = DiscreteGaussianDistributionIntegerSampler(sigma=sigma_demo)
s_demo = random_vector(Zq, n)
A_demo = random_matrix(Zq, m, n)
e_demo = vector(Zq, [D_demo() for _ in range(m)])
b_demo = A_demo * s_demo + e_demo

# What Gaussian elimination returns
s_gauss = A_demo[:n].solve_right(b_demo[:n])

print(f'True secret s:         {s_demo}')
print(f'Gauss elimination:     {s_gauss}')
print(f'Match: {s_gauss == s_demo}')
print(f'\nError vector (signed): {[to_signed(ei, q) for ei in e_demo]}')
print(f'Max |error|: {max(abs(to_signed(ei, q)) for ei in e_demo)}')
print(f'\nDifference s - s_hat (mod q): {s_demo - s_gauss}')
print(f'\nThe Gaussian elimination output is GARBAGE, it bears no')
print(f'resemblance to the true secret, even though the noise entries')
print(f'are at most ~{3*sigma_demo:.0f} out of q={q}.')

The Fix: Use Proper Noise

The noise parameter $\sigma$ must satisfy two constraints:

Security: $\sigma \ge \sqrt{n}$ (Regev's reduction requires this for worst-case lattice hardness). Larger $\sigma$ gives stronger security.
Correctness: $\sigma$ must be small enough that decryption works. The decryption error probability depends on $\sigma \cdot \sqrt{n} / q$ . This ratio must be kept below a threshold (roughly $< 1/4$ ).

For Kyber (ML-KEM), the error uses a centered binomial distribution $\text{CBD}_\eta$ with parameter $\eta \in \{2, 3\}$ , giving integer noise in $\{-\eta, \ldots, \eta\}$ with standard deviation $\sigma = \sqrt{\eta/2}$ . Combined with $n = 256$ and $q = 3329$ , this gives a decryption failure probability below $2^{-139}$ .

The moral: Noise is not overhead --- noise IS the security. Without it, you have a system of linear equations, and linear equations are easy.

In [ ]:

# === Exercise: Explore the noise threshold more finely ===
#
# For n=6 and q=67, find the smallest sigma (to 1 decimal place)
# at which Gaussian elimination drops below 10% success rate.
#
# Hint: test sigma in [0.0, 0.2, 0.4, 0.6, 0.8, 1.0, 1.2, ...]

n_ex = 6
m_ex = 10
q_ex = 67
Zq_ex = Zmod(q_ex)
num_ex_trials = 100

fine_sigmas = [i * 0.2 for i in range(16)]  # 0.0 to 3.0
fine_results = []

for sig in fine_sigmas:
    wins = 0
    for _ in range(num_ex_trials):
        s_ex = random_vector(Zq_ex, n_ex)
        A_ex = random_matrix(Zq_ex, m_ex, n_ex)
        if sig == 0:
            e_ex = zero_vector(Zq_ex, m_ex)
        else:
            D_ex = DiscreteGaussianDistributionIntegerSampler(sigma=float(sig))
            e_ex = vector(Zq_ex, [D_ex() for _ in range(m_ex)])
        b_ex = A_ex * s_ex + e_ex
        try:
            s_guess_ex = A_ex[:n_ex].solve_right(b_ex[:n_ex])
            if s_guess_ex == s_ex:
                wins += 1
        except Exception:
            pass
    rate = wins / num_ex_trials
    fine_results.append((sig, rate))
    marker = ' <--- below 10%' if rate < 0.10 and (len(fine_results) < 2 or fine_results[-2][1] >= 0.10) else ''
    print(f'sigma={sig:>4.1f}: recovery rate = {rate:>5.0%}{marker}')

p_fine = list_plot(fine_results, plotjoined=True, marker='o',
                   color='steelblue', thickness=2)
p_fine += line([(0, 0.1), (3.0, 0.1)], color='red', linestyle='--',
               legend_label='10% threshold')
p_fine.axes_labels(['$\\sigma$', 'Recovery rate'])
show(p_fine, figsize=(8, 4), title=f'Fine-grained noise threshold (n={n_ex}, q={q_ex})')

Summary

Noise level	Attack	Outcome
$\sigma = 0$	Gaussian elimination	Instant break
$\sigma$ tiny ( $< 1$ )	Gaussian elimination	Occasional success, mostly fails
$\sigma$ moderate ( $\approx 1{-}3$ )	Gaussian elimination	Complete failure
$\sigma \ge \sqrt{n}$	All known algorithms	Conjectured hard

Key takeaways:

Without noise, LWE is just a system of linear equations --- solvable in polynomial time by Gaussian elimination.
The error term $\mathbf{e}$ is the sole source of hardness in LWE. It transforms the problem from $O(n^3)$ to (conjectured) exponential.
Over $\mathbb{Z}_q$ , even a single unit of error per equation is enough to destroy Gaussian elimination, because modular arithmetic amplifies errors catastrophically during back-substitution.
Proper noise parameters ( $\sigma \ge \sqrt{n}$ , centered binomial for Kyber) are not optional --- they are the security mechanism itself.
Noise is the only thing standing between your secret and Gaussian elimination.

Back to Module 08: Lattices and Post-Quantum Cryptography