Introduction

Give a high-schooler a stack of linear equations — 3x + 5y = 11, 2x + 7y = 16, and so on — and they can grind out the unknowns with elimination. With enough clean equations, recovering a hidden vector of numbers is fast, exact and boring. Computers do it in the blink of an eye.

Now play one cruel trick: after computing each equation's right-hand side, nudge it by a small random amount. Just a little — 11 becomes 12, 16 becomes 15. Every equation is now almost right, but none is exactly right, and you are never told which way each was nudged.

That tiny smudge is devastating. Elimination amplifies the errors until the answer is pure garbage. This is the Learning With Errors problem (LWE), and the gap between "solve clean equations" and "solve noisy ones" is one of the sharpest easy-vs-hard cliffs in all of computing.

Try It Yourself

Below, a secret vector s is hidden. The computer publishes equations of the form a·s + e = b (mod q) — each aa is a public random row, bb is the result, and ee is a small secret error. Toggle the noise on and off and watch what happens when you ask a solver to recover s.

<p class="hint">A secret <b>s = (s&#8321;, s&#8322;)</b> is hidden. Each row is an equation
    <b>a&#183;s + e = b (mod 7)</b>: <span class="mono">a</span> is public, <span class="mono">b</span>
    is the result, and <span class="mono">e</span> is a small secret error (only when noise is on).
    Checking a guess is instant; recovering the secret is the hard part.</p>
<div class="ctrl">
  <label class="switch"><input type="checkbox" id="noise"> Noise <b id="noiseLbl">OFF</b></label>
  <button id="newp" type="button" class="ghost">New problem</button>
</div>
<table class="eqs" id="eqs"></table>
<div class="guess">
  Your guess: s&#8321;=<select id="g0"></select> s&#8322;=<select id="g1"></select>
</div>
<div class="status" id="status">Toggle noise, then verify or solve.</div>
<div class="btns">
  <button id="check" type="button">Verify my guess</button>
  <button id="solve" type="button">Solve it for me</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
.mono { font-family: ui-monospace, monospace; }
.ctrl { display: flex; align-items: center; gap: 1rem; flex-wrap: wrap; margin: .2rem 0 .6rem; }
.switch { font-size: .9rem; font-weight: 600; display: inline-flex; align-items: center; gap: .4rem; cursor: pointer; }
.eqs { border-collapse: collapse; font: 600 15px ui-monospace, monospace; margin: .3rem 0 .6rem; }
.eqs td { padding: .25rem .55rem; border-bottom: 1px solid #e3e8ee; white-space: nowrap; }
.eqs td.b { color: #1d3557; }
.eqs td.e { color: #c92f3c; font-size: 13px; }
.guess { font-size: .95rem; margin: .4rem 0; }
select { font: 600 14px ui-monospace, monospace; padding: .15rem .3rem; }
.status { font-size: 1rem; font-weight: 600; margin: .5rem 0; min-height: 1.4em; }
.status.ok { color: #0a7d33; }
.status.bad { color: #c92f3c; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Learning With Errors (toy): secret s in (Z_7)^2. Each equation is a row a,
    // with b = (a.s + e) mod 7. With noise OFF, e = 0 and the system is exactly
    // solvable (clean linear algebra). With noise ON, e in {-1,0,1} so every b is
    // only APPROXIMATELY right: elimination breaks, but VERIFYING a guess is easy
    // (each residual must stay within the error bound). Recovering s in general is
    // as hard as worst-case lattice problems (Regev, 2005). Here n=2,q=7 so brute
    // force over q^n = 49 secrets still works — that's the whole point: it only
    // stays feasible because the toy is tiny.
const Q = 7, N = 2, ROWS = 4, BOUND = 1; // |e| <= BOUND when noise on
const mod = x => ((x % Q) + Q) % Q;
const rint = n => Math.floor(Math.random() * n);

let secret, rowsA, errs, bVals, noise = false;

function genProblem(){
  secret = [1 + rint(Q - 1), 1 + rint(Q - 1)]; // nonzero-ish secret
  rowsA = []; errs = []; bVals = [];
  for(let i = 0; i < ROWS; i++){
    const a = [rint(Q), rint(Q)];
    const e = noise ? (rint(2 * BOUND + 1) - BOUND) : 0; // -1..1 or 0
    const b = mod(a[0] * secret[0] + a[1] * secret[1] + e);
    rowsA.push(a); errs.push(e); bVals.push(b);
  }
}

function renderEqs(){
  const t = document.getElementById('eqs'); t.innerHTML = '';
  for(let i = 0; i < ROWS; i++){
    const tr = document.createElement('tr');
    const a = rowsA[i];
    tr.innerHTML = '<td>' + a[0] + '·s₁ + ' + a[1] + '·s₂'
      + (noise ? ' + e' : '') + '</td>'
      + '<td>≡</td><td class="b">' + bVals[i] + ' (mod 7)</td>'
      + (noise ? '<td class="e">e=' + (errs[i] >= 0 ? '+' : '') + errs[i] + '</td>' : '<td></td>');
    t.appendChild(tr);
  }
}
function fillSelects(){
  ['g0','g1'].forEach(id => {
    const s = document.getElementById(id); s.innerHTML = '';
    for(let v = 0; v < Q; v++){ const o = document.createElement('option'); o.value = v; o.textContent = v; s.appendChild(o); }
  });
}
function setStatus(t, cls){ const s = document.getElementById('status'); s.textContent = t; s.className = 'status ' + cls; }

// A candidate secret g is ACCEPTED iff every residual b-(a.g) reduces, mod q,
    // to something within [-BOUND, BOUND] (i.e. a small error could explain it).
function residual(g, i){
  let r = mod(bVals[i] - (rowsA[i][0] * g[0] + rowsA[i][1] * g[1]));
  if(r > Q / 2) r -= Q; // map to (-q/2, q/2]
  return r;
}
function accepts(g){
  const tol = noise ? BOUND : 0;
  for(let i = 0; i < ROWS; i++) if(Math.abs(residual(g, i)) > tol) return false;
  return true;
}

function check(){
  const g = [+document.getElementById('g0').value, +document.getElementById('g1').value];
  if(accepts(g)){
    if(g[0] === secret[0] && g[1] === secret[1])
      setStatus(fmt('✓ (%g%) is the secret — every equation checks out.', { g: g }), 'ok');
    else
      setStatus(fmt('✓ (%g%) also fits within the noise. Verifying is easy!', { g: g }), 'ok');
  } else {
    setStatus(fmt('✗ (%g%) breaks at least one equation. Keep searching.', { g: g }), 'bad');
  }
}

// "Solve" = brute force over all q^n secrets (only feasible because it's tiny).
function solve(){
  const found = [];
  let steps = 0;
  for(let x = 0; x < Q; x++) for(let y = 0; y < Q; y++){
    steps++;
    if(accepts([x, y])) found.push([x, y]);
  }
  if(found.length === 0){ setStatus('No secret fits — try a new problem.', 'bad'); return; }
  const hit = found.find(g => g[0] === secret[0] && g[1] === secret[1]) || found[0];
  document.getElementById('g0').value = hit[0];
  document.getElementById('g1').value = hit[1];
  const tag = noise
    ? fmt('searched all %steps% secrets; %length% fit the noisy clues. Real qⁿ is astronomical.', { steps: steps, length: found.length })
    : fmt('searched all %steps% secrets; the clean system pins down exactly one.', { steps: steps });
  setStatus(fmt('Found s = (%hit%) — %tag%', { hit: hit, tag: tag }), 'ok');
  console.log('secret', secret, 'candidates', found, 'steps', steps);
}

function rebuild(){
  noise = document.getElementById('noise').checked;
  document.getElementById('noiseLbl').textContent = noise ? 'ON' : 'OFF';
  genProblem(); renderEqs();
  setStatus('Toggle noise, then verify or solve.', '');
}

document.getElementById('noise').addEventListener('change', rebuild);
document.getElementById('newp').addEventListener('click', rebuild);
document.getElementById('check').addEventListener('click', check);
document.getElementById('solve').addEventListener('click', solve);
fillSelects();
rebuild();
Result
Console

With noise off, the equations are exact: pick the rows you need, solve, and the secret pops out instantly. Turn noise on and the same solver returns nonsense — yet you can still verify a guess in a heartbeat by plugging it back in and checking every equation stays within the error margin. Checking is easy; recovering is hard. Brute force over all secrets works for q = 7 and two unknowns, but the search space is qnq^{n} — multiply the size and it explodes beyond any computer.

The Real Complexity

How hard is recovering the secret, really?

  • Checking a candidate secret is trivial: compute a⋅sa \cdot s for every published row and confirm each result lands within the small error window of bb. Linear time.
  • Brute force scans all qnq^{n} possible secrets — fine for a toy q = 7, n = 2, hopeless once nn is in the hundreds and qq in the thousands, as in real systems.
  • Gaussian elimination fails the moment noise is present: combining equations sums their errors, and after a few steps the accumulated noise swamps the signal entirely.
  • The landmark result. In 2005 Oded Regev proved that solving LWE on average is at least as hard as solving notoriously hard lattice problems (such as the decision shortest-vector problem, GapSVP) in the worst case. The reduction is quantum — and crucially, no efficient quantum algorithm is known for those lattice problems either.

That worst-case-to-average-case guarantee is the prize. For most cryptographic assumptions you only hope a random instance is hard; for LWE, breaking a typical key would break the hardest lattice instance that exists. It is the same "verify in a flash, solve seemingly never" tension that animates P vs NP, but with a security proof attached.

Where It Matters

The noise that ruins elimination is exactly what makes LWE a building material for cryptography:

  • Post-quantum encryption. Shor's algorithm would let a quantum computer shatter RSA and elliptic curves, but not lattice problems. NIST's flagship standard Kyber (ML-KEM) and the signature scheme Dilithium (ML-DSA) are both LWE-style.
  • Homomorphic encryption. Because LWE ciphertexts carry a noise term that behaves predictably under addition and multiplication, they let you compute directly on encrypted data — the basis of fully homomorphic encryption.
  • Key exchange at scale. Lightweight LWE variants (Ring-LWE, Module-LWE) already protect real TLS connections in browsers experimenting with quantum-safe handshakes.
  • A bridge from cryptography to learning theory. LWE descends from the "learning parity with noise" problem, tying it to the limits of PAC learning and what noisy data can ever reveal.

Whenever a system must stay secret even against a future quantum adversary, there is a good chance noisy lattice equations are doing the guarding — close cousins of the discrete logarithm assumptions they are designed to outlive.

Conclusion

Learning With Errors is a small idea with enormous reach: take equations a child could solve, blur each answer by a hair, and you obtain a problem we believe even quantum computers cannot crack. Verifying a secret stays instant; recovering it is tied, by Regev's reduction, to the hardest lattice problems known.

So the next time you hear that the internet is bracing for "quantum-safe" cryptography, picture the unglamorous hero behind it — not an exotic gadget, but a deliberate sprinkle of noise. It is intractability turned into armor, and another face of the same P vs NP frontier that runs through all of computer science.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/learning-with-errors/Content licensed under CC BY-NC 4.0.