Kyber & Dilithium

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.

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">
  {{hint}}
</p>
<div class="panel">
  <div class="row">
    <label>{{label_secret}}</label>
    <input type="range" id="secret" min="0" max="15" value="7">
    <span id="secretVal" class="val">7</span>
  </div>
  <div class="row">
    <label>{{label_noise}}</label>
    <input type="range" id="noise" min="0" max="24" value="3">
    <span id="noiseVal" class="val">3</span>
  </div>
  <div class="row">
    <label>{{label_msgbit}}</label>
    <div class="toggles">
      <button id="msg0" class="tog active" onclick="setMsg(0)">{{btn_bit0}}</button>
      <button id="msg1" class="tog" onclick="setMsg(1)">{{btn_bit1}}</button>
    </div>
  </div>
</div>
<div id="samples" class="samples"></div>
<div id="status" class="status"></div>
<div class="btns">
  <button id="btnGen" type="button">{{btn_generate}}</button>
  <button id="btnDecrypt" type="button">{{btn_decrypt}}</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; }

// Code not found

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.

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.

"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.

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.