Skip to content

TL;DR — read this first

A reused public key quietly loses security — no attack required

It never throws an error. The handshake still succeeds and the ciphertext still decrypts — yet, quietly, the security margin you were promised is draining away. Code-based KEMs (BIKE, HQC, Classic McEliece) rest on the hardness of syndrome decoding. Each time you reuse one public key for another session, an attacker collects another syndrome — and decoding one out of many gets cheaper. Reuse a key for D sessions and its effective security falls by about ½·log₂(D) bits.

The trap Nothing breaks and nothing warns you. A single key reused for 2¹¹ sessions (BIKE) or 2²¹ (Classic McEliece) has already slipped below the very NIST Level-1 bar the scheme was certified at — silently. Single-session security is untouched; the only fix is to rotate keys on a schedule tied to traffic.

Who's tempted to reuse one key

  • Firmware / IoT — a KEM key burned into a device and used for years without rotation.
  • Cached server keys — one TLS/HPKE key reused across millions of handshakes between rotations.
  • Published prekeys — a static messaging prekey senders reuse until it is replenished.
  • One key over a big archive — a whole backup corpus encrypted to a single long-term recipient key.

The safer pattern

  • Prefer ephemeral keys — a fresh keypair per session. Then D = 1 and there is nothing to drain.
  • If a static key is unavoidable, rotate on session volume, not just the calendar — the calculator below turns your traffic rate into a cadence.
  • Keep a bit-margin above the floor to absorb rounding and the model-vs-paper gap.

1 See it

The erosion, as you reuse one public key

Drag D — the number of session keys derived from a single public key — and watch effective security drain toward the 143-bit Level 1 floor.

D = 1 = 20

Jump to:
Effective classical security (bits) vs. log₂(D) for HQC-1, BIKE-1 and mceliece3488-64. The red line is the 143-bit Level-1 floor. A full textual description of the current state is available to screen readers below.
Scheme Effective bits Margin to floor Status

idealized √D model These effective-bit and margin numbers come from the simplified law T₁ − ½·log₂(D) — not the paper's full-ISD tables. On the chart, the filled dot ● marks this model's crossover and the hollow diamond ◇ marks the paper's. For Classic McEliece the two visibly differ; trust the earlier (more conservative) of the two.

2 First, the word everything hinges on

What is a syndrome?

The whole demo above counts syndromes — so before we count them, let's see one. A syndrome is a short fingerprint of a hidden error. Flip some bits in the toy code below and watch its fingerprint change.

Take a real (tiny) error-correcting code: the [7, 4] Hamming code. An error vector e is 7 bits — a 1 wherever a bit got flipped in transit. The code has a parity-check matrix H (3 rows). The syndrome is just s = H·e over GF(2): each syndrome bit is the parity (XOR) of the error bits in that row of H. Three bits that summarise seven.

Error vector e — click a bit to flip it

Weight (bits flipped): 0

H · e = s  (each row: XOR of the flipped bits it covers)

syndrome s = 000

Now the catch — decoding is ambiguous:

Both patterns produce the identical syndrome, so H alone cannot tell them apart. Decoding is therefore not "find an error" but "find the lowest-weight error for this syndrome" — the fewest flips that explain the fingerprint. That search is the hard problem all three KEMs stand on. Everything below is about how reusing a key hands the attacker many syndromes at once, and why that makes the search cheaper.

3 The bargain that drains it

Why more targets make each one cheaper (the √M idea)

Here is the intuition the numbers rest on. Decoding one syndrome is hard because the attacker must guess-and-check candidate errors until one fits. Holding M syndromes at once doesn't make any single one easier — it means every guess is checked against all M targets simultaneously, so a hit is M× more likely per guess.

Each dot is one target syndrome the attacker holds. A single “sweep” of guessing (the moving band) lands a hit whenever it touches any target — so more targets means more hits for the same work. A full textual description is available to screen readers below.

1 target (= 20)

  • Work to land one hit scales like √M, not M — the classic birthday-style bargain: doubling the targets only halves the square root's exponent's growth, buying a ½-bit discount per doubling.
  • In bits, holding M targets is worth −½·log₂(M) off the attacker's cost. That is exactly the DOOM law the chart uses, now with a picture behind it.
  • Reuse count on the chart: D = 2⁰ → attacker holds ≈ M syndromes → discount −0.0 bits. (Drag D above; this follows it.)

The dots are a faithful cartoon of a real amortised ISD search, not the search itself (the demo runs no attack). The point is only the shape: probability of a hit rises with the number of targets, so cost per hit falls as √M. Precise per-scheme figures come from the paper's tables, transcribed in the reference card below.

4 Understand it

Why it drains: the DOOM lever

You just met both halves of this. All three KEMs rest on syndrome decoding: given a parity-check matrix and a syndrome, find the low-weight error that produces it (Step 2). Decoding One Out of Many (DOOM, Sendrier) says that if you hold M syndromes for the same matrix, decoding any one of them costs about √M less — a saving of ½·log₂(M) bits (Step 3). The attacker's best tool for that search is MMT, one member of the ISD family.

The quasi-cyclic ring F₂[X]/(Xⁿ − 1) behind HQC and BIKE already hands an attacker n syndromes from a single key (each cyclic shift Xʲ is another instance). That √n saving was already spent when these schemes' Level-1 parameters were chosen. The new result asks a different question: what happens when one public key is reused for D sessions?

BIKE re-harvests its whole ring every session (≈ n·D), while HQC's reduction blocks the ring (≈ D) — to cancel the message it multiplies by P′·T_ℓ, which destroys the cyclic structure, so the n shifts no longer yield valid syndromes — and Classic McEliece has no ring at all (≈ D). Because n is a constant, that richer harvest is a fixed head-start already folded into BIKE's single-instance number — so all three lose ½ bit per doubling of D, and the scheme that starts with the thinnest margin (BIKE) hits the floor first.

5 Act on it

Key-rotation policy calculator

The operational takeaway: rotate public keys on a schedule tied to session volume. Set a security target and a per-key session budget; this tells you how much head-room each scheme has.

Default = NIST Level-1 floor (143).

Extra head-room you require beyond the floor.

≈ 220.0 sessions.

Used to turn a safe-D limit into a rotation cadence.

Try a realistic scenario: (sets the budget to one year at that rate)
Scheme Max safe D (rotate before) Rotate at least every Your budget vs. limit

idealized √D model "Max safe D" is computed from the same simplified √D law as the chart. Where the paper's full-ISD crossover sits higher (Classic McEliece: paper 2²¹ vs the model's ≈2¹⁷), the model is the more conservative bound — it tells you to rotate sooner, which is the safe direction to err.

Reference

Parameters & sources

Every number above traces to a published value. Here is each scheme's inputs with its citation — chase any of them.

Show the sourced inputs (Level 1)
Scheme Single-inst T₁ (MMT) Code length n Syndromes / D Paper crossover Source
How to verify this yourself

Every curve is one line of arithmetic. Effective classical security at reuse count D is: 

effective_bits(D) = T1 - 0.5 * log2(D)

Plug in each scheme's published single-instance MMT complexity T₁ (HQC-1 = 160.04, BIKE-1 = 148.17, mceliece3488-64 = 151.22) and the NIST Level-1 floor of 143 bits. The crossover is where it hits the floor: 

crossover_log2D = 2 * (T1 - 143)

That gives BIKE ≈ 2¹¹, McEliece ≈ 2¹⁷ (model) and HQC ≈ 2³⁴. Cross-check against the paper's full-ISD tables (Abstract and Tables 2 / 5 / 7), which state 2¹¹, 2²¹ and 2³⁴ respectively — the McEliece gap is the model-vs-reality slope difference, flagged throughout. Sources: ePrint 2026/517 (the √M / DOOM law is §2 and Figs 2–5; the per-scheme tables are §3.1, §4.1, §5.1), and the pure implementation in src/model.ts.

Good to know

Common misconceptions

The fast version of this result is easy to over- or under-read. Five quick clarifications.

“Doesn't this mean the KEM is broken?”
No. Per-instance syndrome decoding is exactly as hard as before — nothing here breaks the underlying problem. This is multi-instance amortization: it only shows up when one key is reused for many sessions, and rotating the key restores the full security level.
“Is single-session security still fine?”
Yes. At D = 1 the effective security equals the full single-instance value T₁. The drain needs many sessions derived from the same public key; a key used once loses nothing.
“Why isn't this as bad for Kyber / ML-KEM?”
Lattice-based KEMs like ML-KEM are not vulnerable to this specific form of security degradation. The DOOM attack relies on collecting many syndromes for the same key under a code-based scheme; lattice KEMs have a different mathematical structure, so this particular attack path does not apply. That said, lattice schemes have their own multi-target analyses in the literature — they are simply different in character from DOOM-style syndrome-decoding attacks.
“So I should never reuse a public key?”
Reuse is fine up to a budget. The point isn't “never reuse” — it's “bound D and rotate before the floor.” The rotation calculator turns your traffic into a concrete safe budget and cadence.
“Is the √D line the real security?”
It's an idealized model (slope exactly ½). The paper's full-ISD numbers differ — most visibly for Classic McEliece, whose real ISD slope (≈0.39) is shallower. The chart plots both crossovers so you never have to trust one blindly; when they disagree, prefer the more conservative.

Caveats

Known gaps & honest caveats

  • This is asymptotic multi-instance degradation, not a break of syndrome decoding. Per-instance hardness is intact; the schemes remain sound when public keys are rotated.
  • Numbers are computed from published Level-1 parameters and the paper's √D law. The demo runs no decoding and no DOOM.
  • v1 covers NIST Level 1 only (HQC-1, BIKE-1, mceliece3488-64).
  • No values are currently marked UNKNOWN for the Level-1 model. The DS (Dumer–Stern) single-instance figures are not displayed; MMT — the attacker's best variant — drives every number shown.