Introduction

Every time you open a website over HTTPS, your browser and the server silently exchange a secret key. The security of that exchange today rests on a simple assumption: factoring large numbers or computing discrete logarithms is too hard for any computer that exists.

That assumption has an expiration date. A large enough quantum computer running Shor's algorithm (1994) can factor any number and compute any discrete log in polynomial time — breaking RSA, Diffie-Hellman, and elliptic-curve cryptography in one stroke.

The question is not if such a machine arrives, but when. Cryptographers started preparing decades ago. In 2024 NIST finalized the answer: ML-KEM (Kyber) for key encapsulation and ML-DSA (Dilithium) for digital signatures. Both are built on a mathematical structure called a lattice, and they owe their security to a problem so tangled that no quantum algorithm is known to crack it.

Hiding Secrets in Noise

The heart of both Kyber and Dilithium is a primitive called Learning With Errors (LWE). The idea: take a secret number, multiply it by a public value, then add a tiny random error before publishing. The receiver who knows the secret can strip the noise away; everyone else sees only scrambled data.

<p class="hint">
  This demo shows <b>Learning With Errors (LWE)</b>, the core of Kyber &amp; Dilithium.
      Alice publishes pairs <code>(a, b = a·s + e mod 64)</code> where <code>s</code> is her
      secret and <code>e</code> is random noise. Bob uses <code>s</code> to strip the noise
      and recover her hidden message bit.
</p>
<div class="panel">
  <div class="row">
    <label>Secret <code>s</code>&nbsp;(0–15)</label>
    <input type="range" id="secret" min="0" max="15" value="7">
    <span id="secretVal" class="val">7</span>
  </div>
  <div class="row">
    <label>Noise level <code>σ</code>&nbsp;(0–24)</label>
    <input type="range" id="noise" min="0" max="24" value="3">
    <span id="noiseVal" class="val">3</span>
  </div>
  <div class="row">
    <label>Message bit to hide</label>
    <div class="toggles">
      <button id="msg0" class="tog active" onclick="setMsg(0)">bit 0</button>
      <button id="msg1" class="tog" onclick="setMsg(1)">bit 1</button>
    </div>
  </div>
</div>
<div id="samples" class="samples"></div>
<div id="status" class="status"></div>
<div class="btns">
  <button id="btnGen" type="button">Generate new samples</button>
  <button id="btnDecrypt" type="button">Decrypt with secret s</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; font-size: 14px; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .8rem; line-height: 1.5; }
.panel { background: #f0f4f8; border-radius: 10px; padding: .7rem 1rem; margin-bottom: .8rem; }
.row { display: flex; align-items: center; gap: .6rem; margin: .35rem 0; flex-wrap: wrap; }
label { font-size: .82rem; color: #555; min-width: 11rem; }
input[type=range] { flex: 1; min-width: 100px; accent-color: #1d3557; }
.val { font: 700 1rem ui-monospace, monospace; min-width: 2.4rem; color: #1d3557; }
.toggles { display: flex; gap: .4rem; }
.tog { padding: .3rem .75rem; border: 1.5px solid #1d3557; background: #fff;
       color: #1d3557; border-radius: 6px; cursor: pointer; font-weight: 700; font-size: .9rem; }
.tog.active { background: #1d3557; color: #fff; }
.samples { display: grid; grid-template-columns: repeat(5, 1fr); gap: 5px; margin-bottom: .6rem; }
.sample { background: #e8eef3; border-radius: 7px; padding: .35rem .4rem; text-align: center;
          font: 600 .75rem ui-monospace, monospace; line-height: 1.7; border: 1px solid #cdd9e3; }
.sample .a { color: #777; font-size: .7rem; }
.sample .b { color: #1d3557; }
.sample.ok { background: #d4edda; border-color: #7ec8a4; }
.sample.err { background: #fde8e8; border-color: #e09090; }
.sample .dec { font-size: .8rem; font-weight: 800; }
.status { font-size: .95rem; font-weight: 600; margin: .4rem 0 .6rem; min-height: 1.3em; }
.status.ok { color: #0a7d33; }
.status.warn { color: #b45309; }
.status.bad { color: #c92f3c; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 13px system-ui; padding: .42rem .85rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Learning With Errors (LWE) toy demo — works over Z_64 (q=64).
//
// Encoding a message bit m:
//   pick random a in [0,63]
//   compute b = (a * s  +  e  +  m * 32) mod 64
//   publish (a, b)      where e = uniform random noise in [-sigma, sigma]
//
// Decoding with the secret s:
//   compute v = (b - a*s) mod 64
//   v should be near  0 if m=0,  or near 32 if m=1
//   decide by which half of [0,64) v falls in
//
// The security: without knowing s, the pair (a,b) is computationally
// indistinguishable from random — that is the LWE assumption.
// Noise is necessary: without it, a linear system in s is easy to solve.
// Too much noise makes even the legitimate receiver fail to decode.

const Q = 64;
const N = 10;
let secret = 7, noiseLevel = 3, msgBit = 0;
let samples = [];

function mod(x, m) { return ((x % m) + m) % m; }

// Uniform integer noise in [-sigma, sigma]
function randNoise(sigma) {
  if (sigma === 0) return 0;
  return Math.round((Math.random() * 2 - 1) * sigma);
}

function randInt(lo, hi) { return lo + Math.floor(Math.random() * (hi - lo + 1)); }

function generate() {
  samples = [];
  for (let i = 0; i < N; i++) {
    const a = randInt(0, Q - 1);
    const e = randNoise(noiseLevel);
    // m=1 shifts by Q/2=32, m=0 shifts by 0
    const b = mod(a * secret + e + msgBit * (Q >> 1), Q);
    samples.push({ a, b });
  }
  renderSamples(false);
  setStatus(
    fmt('Generated 10 LWE samples. s=%secret%, σ=%noiseLevel%, bit=%msgBit%. %v%', { secret: secret, noiseLevel: noiseLevel, msgBit: msgBit, v: noiseLevel <= 8 ? 'Noise is small — receiver can decode.' :
     noiseLevel <= 16 ? 'Noise is borderline — try decrypting.' :
     'Noise is large — decoding may fail!' }), ''
  );
}

function decrypt() {
  const half = Q >> 1;  // 32
  let correct = 0;
  const results = samples.map(({ a, b }) => {
    // strip secret contribution
    const v = mod(b - a * secret, Q);
    // distance to 0 (bit=0) vs distance to 32 (bit=1)
    const d0 = Math.min(v, Q - v);
    const d1 = Math.min(Math.abs(v - half), Q - Math.abs(v - half));
    const decoded = d1 < d0 ? 1 : 0;
    if (decoded === msgBit) correct++;
    return decoded;
  });
  renderSamples(true, results);
  const pct = Math.round(correct / N * 100);
  if (correct === N) {
    setStatus(fmt('✓ Bob decoded all %N% samples correctly — noise (σ= σ=%noiseLevel%) stayed within safe range.', { N: N, noiseLevel: noiseLevel }), 'ok');
  } else if (correct >= 7) {
    setStatus(fmt('⚠ Bob decoded %correct%/%N% (%pct%%). Noise is eroding the signal — increase σ further to see more failures.', { correct: correct, N: N, pct: pct }), 'warn');
  } else {
    setStatus(fmt('✗ Bob decoded only %correct%/%N% (%pct%%). Noise σ= σ=%noiseLevel% overwhelms the signal — decryption breaks down.', { correct: correct, N: N, pct: pct, noiseLevel: noiseLevel }), 'bad');
  }
  console.log(
    'LWE decode | secret:', secret, '| sigma:', noiseLevel,
    '| msgBit:', msgBit, '| correct:', correct, '/', N,
    '| decoded:', results.join('')
  );
}

function renderSamples(showDecoded, results) {
  const el = document.getElementById('samples');
  el.innerHTML = '';
  samples.forEach(({ a, b }, i) => {
    const div = document.createElement('div');
    let cls = 'sample';
    if (showDecoded && results) {
      cls += results[i] === msgBit ? ' ok' : ' err';
    }
    div.className = cls;
    div.innerHTML =
      `<div class="a">a=${a}</div>` +
      `<div class="b">b=${b}</div>` +
      (showDecoded && results
        ? `<div class="dec">${results[i] === 1 ? '▪ 1' : '▫ 0'}</div>`
        : '');
    el.appendChild(div);
  });
}

function setStatus(t, cls) {
  const el = document.getElementById('status');
  el.textContent = t;
  el.className = 'status ' + cls;
}

function setMsg(m) {
  msgBit = m;
  document.getElementById('msg0').classList.toggle('active', m === 0);
  document.getElementById('msg1').classList.toggle('active', m === 1);
}

document.getElementById('secret').addEventListener('input', e => {
  secret = +e.target.value;
  document.getElementById('secretVal').textContent = secret;
});
document.getElementById('noise').addEventListener('input', e => {
  noiseLevel = +e.target.value;
  document.getElementById('noiseVal').textContent = noiseLevel;
});
document.getElementById('btnGen').addEventListener('click', generate);
document.getElementById('btnDecrypt').addEventListener('click', decrypt);

generate();
Result
Console

Notice what happens as you increase the noise level: small noise lets the receiver recover the message; large noise overwhelms the signal. The security lives in that gap — the public values look random to an attacker, but the legitimate recipient has the algebraic key to unscramble them. Quantum computers offer no known shortcut through this noise.

The Real Complexity

Both standards belong to the CRYSTALS family (Cryptographic Suite for Algebraic Lattices). Their security reduces to two problems over structured lattices:

  • Module LWE (MLWE) — the core of Kyber. Given many linear equations over a ring with small hidden errors, find the secret vector. No classical or quantum polynomial-time algorithm is known.
  • Module SIS (MSIS) — the core of Dilithium. Find a short vector that satisfies a public linear relation. Also believed quantum-hard.
  • Why lattices resist quantum computers. Shor's algorithm exploits the hidden periodic structure of factoring and discrete logs. Lattice problems have no such periodicity to exploit. The best known quantum attacks offer only a modest speedup over classical ones — nowhere near polynomial time.
  • Status: computationally hard, open to proof. The hardness of MLWE and MSIS is a widely accepted assumption but not a mathematical proof. Breaking them would not solve P vs NP — they are not known to be NP-hard — but decades of cryptanalysis by the best teams in the world have found no efficient attack.
  • NIST standardized both in August 2024 as FIPS 203 (ML-KEM) and FIPS 204 (ML-DSA), making them the first post-quantum standards for general use.

This is the same flavor of bet as RSA — "we believe this is hard" — but aimed at a threat that Shor's algorithm already confirms is coming. See also Learning With Errors for the underlying primitive in detail.

Where It Matters

"Harvest now, decrypt later" is a real threat: adversaries are already storing encrypted traffic today, waiting for a quantum computer powerful enough to break it. That urgency makes migration to post-quantum standards unusually time-sensitive:

  • TLS and HTTPS: Google, Cloudflare, and major browsers began deploying hybrid Kyber in TLS 1.3 in 2023, before the standard was even finalized.
  • VPNs and secure channels: WireGuard and IPSec proposals already carry post-quantum extensions using Kyber.
  • Messaging: Signal added a post-quantum layer (PQXDH) to its X3DH handshake in 2023, using a Kyber-based key agreement.
  • Government and critical infrastructure: NIST's FIPS 203/204 mandate adoption for US federal systems. NATO and the EU have parallel mandates.
  • Hardware security modules (HSMs): Chip manufacturers are embedding ML-KEM and ML-DSA support at the silicon level.
  • Code signing and certificates: Certificate authorities are testing Dilithium-based certificates so software updates remain trustworthy in the quantum era.

The transition is not painless — lattice keys and signatures are larger than RSA ones, and hybrid schemes carry both. But the window for safe migration is finite. See how Shor's algorithm motivates the urgency.

Conclusion

Kyber and Dilithium are the world's answer to a threat that has been visible for thirty years: a quantum computer running Shor's algorithm will shatter the asymmetric cryptography that currently protects almost every secret on the internet.

The solution is elegant — hide secrets inside algebraic noise so fine-grained that no known algorithm, quantum or classical, can sift it out. The mathematics is more intricate than RSA, the keys are larger, and the transition is still ongoing. But the foundations are in place. NIST's 2024 standards mark a rare moment in cryptographic history: a deliberate, community-wide migration to new hard problems before the old ones break.

The next time you open your browser and see a padlock, that padlock may already be lattice-hardened — or it soon will be.

Share this article

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

Comments

Loading comments...

https://www.kipuhub.com/en/article/kyber-dilithium/Content licensed under CC BY-NC 4.0.