The Hedge and Its Fault Line: How Classic McEliece and HQC Would Break

1. A Hedge Against a Single Point of Failure#

In March 2025, having already chosen a lattice-based encryption standard it had spent eight years vetting, NIST did something that looks, at first glance, like betting against its own decision: it selected a second key-encapsulation mechanism, built on a bruised-looking idea from 1978, whose entire job is to fail differently ^[1].

Classic McEliece and its quasi-cyclic cousin HQC do not rest on lattices, or on factoring, or on discrete logarithms. They rest on the difficulty of decoding a random-looking error-correcting code, a problem so unrelated to the others that if lattice cryptography were shattered tomorrow, these schemes would not lose a single bit of security. That independence is the entire point. It is also the thing that tells you exactly where to look for how they would break.

Two standardized KEMs now sit on two unrelated hard problems. ML-KEM, standardized as FIPS 203 in August 2024, reduces to Module-LWE, a lattice problem ^[2]. HQC, selected in March 2025 as the second KEM after ML-KEM, reduces to quasi-cyclic syndrome decoding, a coding problem ^[1]. Behind them stands Classic McEliece, the ultra-conservative elder whose one-wayness assumption "has remained remarkably stable, despite half a century of attack papers" ^[3].

The reason to hold two problems instead of one is written into recent history: vetted finalists fall. Ward Beullens recovered a Rainbow signing key over a single weekend ^[4], and Wouter Castryck and Thomas Decru broke SIKE in an afternoon on one core ^[5]. Each had survived years of scrutiny before one new idea ended it.

flowchart TD
LB["A future break of lattice cryptography"] --> ML["ML-KEM, built on Module-LWE"]
ML --> F1["Lattice-based encryption falls"]
LB -. no known reduction .-> CB["HQC and Classic McEliece, built on syndrome decoding"]
CB --> F2["Code-based encryption stands"]

This article analyzes only the mathematics: how the algorithms themselves would give way under cryptanalysis. Side-channel leaks, fault injection, random-number failures, and protocol misuse are real, but they attack an implementation, not the problem, and they belong to the companion piece "How the NIST Finalists Broke."

Two fault lines belong here. The first is information-set decoding, the generic attack that prices every code-based parameter. The second is a structural distinguisher, an algorithm that would notice the code is not random after all. If a lattice break truly does not touch these schemes, what exactly would? To answer that, you first have to see why the two hard problems are strangers.

2. Two Hard Problems, Not One#

What makes two hard problems independent enough that betting on both is safer than betting on one? Not that both are hard. Independence means a solution to one buys you nothing against the other. That is a strong claim, and code-based cryptography earns it honestly.

Start with the problem itself. An error-correcting code adds redundancy so a receiver can repair a noisy message. A parity-check matrix $H$ describes the redundancy: a vector is a valid codeword exactly when $H$ maps it to zero. Feed $H$ a corrupted word instead, and it returns a short fingerprint of the corruption called the syndrome. The attacker's task is to run that backward.

In 1978, the same year McEliece published his cipher, Elwyn Berlekamp, Robert McEliece, and Henk van Tilborg proved that this decoding problem is NP-complete ^[6]. That badge is the strongest worst-case anchor any deployed public-key system has. It is also, we will see in section 12, a promise the schemes cannot fully cash: NP-completeness is a statement about the worst case, while the deployed schemes rest on the average case of a specific structured family, and no reduction bridges the two. Hold that thought; the honest security story lives there.

The syndrome you are chasing is a concrete object. Here is one small enough to hold in your hand.

# Parity-check matrix H (4 x 7) over F2, and a weight-2 error e.
H = [
  [1, 0, 0, 1, 0, 1, 1],
  [0, 1, 0, 1, 1, 0, 1],
  [0, 0, 1, 0, 1, 1, 1],
  [1, 1, 0, 0, 1, 0, 0],
]
e = [0, 1, 0, 0, 0, 1, 0]   # Hamming weight 2

# Syndrome s = H . e^T, each entry reduced mod 2.
s = [sum(H[i][j] * e[j] for j in range(len(e))) % 2 for i in range(len(H))]
print("error weight:", sum(e))
print("syndrome s   :", s)
# The attacker sees only H and s, and must recover the weight-2 e.
# Doing that with no trapdoor is information-set decoding.

Now the independence claim. Lattice cryptography, the subject of Part 6 of this series, rests on problems like Learning With Errors, where you recover a secret from noisy linear equations over a large modulus. Syndrome decoding lives over $\mathbb{F}_2$ and measures noise by Hamming weight, not Euclidean distance. There is no known reduction in either direction between the two, and "no known reduction" is the exact, non-overstated phrasing: not a proof of independence, but the honest state of decades of trying ^[7].

The two worlds do share some tooling. The fastest modern decoders and the fastest lattice sieves both reduce, deep down, to nearest-neighbor search ^[8]. That is a shared algorithm, not a shared assumption: a faster nearest-neighbor routine nudges both cost estimates, but it does not let a lattice break read out a code secret.

Because syndrome decoding has no known reduction to or from lattice problems, a break of lattice cryptography does not debit code-based cryptography. The hedge is not a slogan. It is the absence of a mathematical bridge between the two assumptions.

So the hardness is real and, as far as anyone knows, unrelated to the lattice bet. But hardness alone is not a cipher. Turning "decoding a random code is hard" into public-key encryption took a specific 1978 trick: hiding a code you can secretly decode.

3. A Stranger Question: McEliece (1978) and Niederreiter (1986)#

RSA had appeared in 1977, founding public-key encryption on number theory ^[9]. Robert McEliece, then a staff member at NASA's Jet Propulsion Laboratory, which Caltech operates for NASA and where coding theory was daily bread for talking to deep-space probes, asked a stranger question the very next year: could you build public-key encryption on coding theory instead? The 1978 scheme is a JPL publication, not a Caltech academic paper. McEliece worked at JPL through 1978, was a professor at the University of Illinois at Urbana-Champaign from 1978 to 1982, and joined the Caltech electrical-engineering faculty only in 1982 ^{[10, 11]}.

His answer, published in a JPL progress report rather than a cryptography venue, is the oldest public-key encryption scheme whose underlying hardness assumption has never been broken, including against a quantum computer ^[12]. RSA, a year older, is still classically secure, so McEliece is not the oldest public-key scheme outright. Its narrower and load-bearing claim to seniority is that its hardness assumption has never fallen, and unlike RSA's factoring assumption it does not fall to Shor's algorithm either ^[13].

The trick is disguise. Take a binary Goppa code, an algebraic code with a secret description that makes error correction fast. Scramble its generator matrix by multiplying on both sides, $G' = SGP$, where $S$ is an invertible matrix and $P$ a permutation. Publish $G'$, which now looks like the generator of a random code.

To encrypt a message $\mathbf{m}$, compute $\mathbf{m}G'$ and add a random error vector $\mathbf{e}$ of Hamming weight $t$. Only the holder of $(S, G, P)$ can undo the scramble and run the fast Goppa decoder to strip the $t$ errors; everyone else faces generic decoding of a code that betrays nothing about its structure ^[3]. McEliece's original parameters used a $[1024, 524]$ Goppa code correcting $t = 50$ errors ^[12].

flowchart TD
G["Secret binary Goppa code, fast decoder"] --> KG["Scramble it: G' = S G P"]
KG --> PK["Publish G' as a random-looking code"]
M["Message m"] --> ENC["Encrypt: c = m G' + e, weight-t error e"]
PK --> ENC
ENC --> DEC["Owner applies S, G, P to peel the disguise"]
DEC --> FD["Secret decoder removes e and returns m"]

Eight years later, Harald Niederreiter published the dual: instead of a scrambled generator matrix, publish a scrambled parity-check matrix $H'$, and let the ciphertext be the syndrome $\mathbf{s} = H'\mathbf{e}^{\top}$ of a low-weight error, with the message encoded into $\mathbf{e}$ ^[15]. With binary Goppa codes the two forms are security-equivalent, but the syndrome form yields smaller ciphertexts, and it is the exact construction Classic McEliece ships today. The object that information-set decoding and the structural distinguishers actually attack is this syndrome form.

For roughly two decades, none of this mattered to practitioners. McEliece's public key ran to hundreds of kilobits, against RSA's hundreds of bits. The scheme was an admired museum piece, correct and elegant and ignored, sidelined by a usability failure rather than a security one. Then in 1994 Peter Shor gave a quantum algorithm that factors integers and computes discrete logarithms efficiently, threatening RSA and elliptic curves, while leaving syndrome decoding with no known handle at all ^[13]. Overnight, "impractical" became "quantum-safe," and the museum piece became an asset.

The McEliece one-wayness problem "has remained remarkably stable, despite half a century of attack papers." -- Classic McEliece official documentation ^[3]

A disguised code and a pile of errors. An attacker who cannot lift the disguise has exactly one other move: decode the public code the hard way. That move has a name, a 1962 origin, and it turns out to set every code-based parameter ever chosen.

4. The Two Ways In: Message Recovery and Key Recovery#

Faced with a McEliece or Niederreiter public key, an attacker has exactly two doors. Everything in the rest of this article walks through one of them, so it is worth naming them cleanly before anyone opens either.

Door 1 is message recovery. Ignore the hidden structure entirely and decode the public code generically, treating it as the random code it pretends to be. Recover the error vector of one ciphertext and you recover one plaintext. This is information-set decoding, and it works against any linear code with no assumptions at all.

Door 2 is key recovery. Instead of decoding a message, tear off the disguise: recover the secret algebraic structure of the code from the public key. Succeed once and you can decrypt every ciphertext ever produced under that key, cheaply, forever. This is the territory of structural and distinguisher attacks.

The two doors differ not just in method but in severity, and that asymmetry is the argument of the whole article. Door 1 is likely but shallow. It has been open, a crack, for sixty years, and all it does when it widens is force the defender to choose bigger parameters. Door 2 is unlikely but deep. No one has walked through it against a deployed parameter set, but if they did, it would not force a parameter change -- it would end the code family.

flowchart TD
PK["A McEliece or Niederreiter public key"] --> D1["Door 1: decode the public code generically"]
PK --> D2["Door 2: recover the hidden code structure"]
D1 --> R1["Information-set decoding, one ciphertext at a time"]
D2 --> R2["Structural distinguisher and key recovery, all ciphertexts at once"]
R1 --> E1["Effect: forces bigger parameters, an erosion"]
R2 --> E2["Effect: ends the whole code family, a collapse"]

Start with Door 1, because it is the door that has actually moved McEliece's numbers, and because its six-decade history is a master class in how a hard problem refuses to collapse.

5. Information-Set Decoding: The Baseline and the Ruler#

Long before McEliece, in 1962, Eugene Prange at the Air Force Cambridge Research Laboratories asked how to decode a code by guessing. Prange published in IRE Transactions on Information Theory; the IRE merged into the IEEE in 1963, so the same journal now carries an IEEE name ^[16]. His answer is still, six decades later, the conceptual core of the fastest known attack on Classic McEliece.

The idea is disarmingly simple. To decode a length-$n$ code, pick $k$ of the $n$ coordinate positions and hope none of the $t$ errors landed on them. If your guess is clean, then within those $k$ coordinates the received word equals the codeword exactly, and a single round of Gaussian elimination reconstructs the message. No search over error patterns, no structure, just linear algebra on a lucky window ^[16].

The catch is the hoping. The chance that a random size-$k$ window is completely error-free is the hypergeometric ratio $\binom{n-t}{k}\big/\binom{n}{k}$: the number of ways to place all $k$ chosen coordinates among the $n-t$ clean ones, over the number of ways to choose any $k$. That probability is tiny, and the expected number of iterations is its reciprocal. Each iteration is cheap and uses only polynomial memory, but you need exponentially many of them, giving a running time around $2^{0.057n}$ in one standard convention ^{[17, 8]}. Run the numbers yourself and watch the exponent climb.

// Log of binomial coefficient C(n, k), to stay numerically sane.
function logChoose(n, k) {
if (k < 0 || k > n) return -Infinity;
let s = 0;
for (let i = 0; i < k; i++) s += Math.log(n - i) - Math.log(i + 1);
return s;
}

// A Prange iteration succeeds if all t errors avoid the size-k information set,
// i.e. every error lands in the remaining n-k coordinates.
function prange(n, k, t) {
const logP = logChoose(n - t, k) - logChoose(n, k); // hypergeometric
return { log2Iters: -logP / Math.LN2 };
}

for (const [n, k, t] of [[100, 50, 10], [200, 100, 20], [400, 200, 40]]) {
const r = prange(n, k, t);
console.log("n=" + n + " k=" + k + " t=" + t +
  "  expected iterations = 2^" + r.log2Iters.toFixed(1));
}

flowchart TD
A["Pick a random size-k information set I"] --> B["Gaussian-eliminate H against I"]
B --> C{"Is I error-free?"}
C -- no --> A
C -- yes --> D["Read the error off by linear algebra, return e"]

Here is the reframe that matters. ISD is not a footnote to code-based cryptography; it is the ruler. Classic McEliece and HQC do not claim a security level derived from a proof. They quote, as their security level, the measured cost of the best known information-set decoder against their public code ^{[3, 9]}. When cryptographers ask "how strong is mceliece6688128," they are asking one question: how many operations does the best ISD need?

Prange's weakness is obvious in hindsight: he throws away every iteration in which even a single error touches the chosen window, and for realistic $t$ that is almost every iteration. Every improvement for the next fifty-six years is a variation on one move: stop demanding a perfectly clean window. How much faster can that make you? Astonishingly little, and that near-flatness is the quiet foundation on which the whole hedge is built.

6. The Evolution of ISD: From Prange to BJMM#

Six decades, some of the sharpest cryptographers alive, and one relentless goal: shave the exponent. Here is the entire distance they traveled, and it is shorter than you would guess.

Each generation kept Prange's skeleton and relaxed his one rigid demand. Lee and Brickell (1988) allowed a few errors to sit inside the information set and paid a small search to find them, so a window no longer had to be perfectly clean ^[18]. Stern (1989) split the window and looked for collisions between two halves, a birthday-style search that became the template for everything modern, at the cost of exponential memory ^[19].

Then the modern jumps. May, Meurer, and Thomae (2011) introduced the representation technique, the first real jump in decades ^[20]. Becker, Joux, May, and Meurer (2012) sharpened it by letting the two halves overlap, exploiting arithmetic over $\mathbb{F}_2$, and reached a headline exponent of $2^{n/20}$ ^[17]. Over $\mathbb{F}_2$, $1+1=0$: if both halves of a representation put a one in the same position, those ones cancel. Allowing that overlap is exactly what multiplies the number of representations in BJMM ^[17]. May and Ozerov (2015) then recast the collision step as approximate nearest-neighbor search ^[8], and Both and May (2018) pushed the same machinery to high error rates, the live frontier ^[21].

Why does counting splittings help? Fix the target error $\mathbf{e}$ of weight $w$ and write it as a sum $\mathbf{e} = \mathbf{e}_1 + \mathbf{e}_2$ of two weight-$w/2$ vectors. The same $\mathbf{e}$ can be written that way in about $\binom{w}{w/2}$ different ways. That abundance is the lever: because so many representations of the one solution exist, the search can impose about $\log_2\binom{w}{w/2}$ extra linear constraints and still expect one representation to survive. Each constraint shrinks the intermediate lists the attacker must build, so more representations buy exponentially smaller lists, and finding a single survivor is enough.

BJMM's $1+1=0$ trick widens the lever: it lets $\mathbf{e}_1$ and $\mathbf{e}_2$ carry ones in positions outside the support of $\mathbf{e}$, where the two ones cancel over $\mathbb{F}_2$, multiplying the representation count from $\binom{w}{w/2}$ to roughly $\binom{w}{w/2}\binom{n-w}{\varepsilon}$ and licensing still more constraints ^[17].

May and Ozerov attack the leftover cost from the other side: the collision step is really a search for two list entries at small Hamming distance, not exact equality, so replacing Stern's exact-match join with an approximate nearest-neighbor search shaves the exponent again ^[8].

flowchart LR
P["Prange 1962"] --> LB["Lee-Brickell 1988"]
LB --> St["Stern 1989"]
St --> MMT["MMT 2011"]
MMT --> BJMM["BJMM 2012"]
BJMM --> MO["May-Ozerov 2015"]
MO --> BM["Both-May 2018"]

Read the table for its shape, not a decimal sequence. Across roughly fifty-six years the exponent constant fell only from about $2^{0.057n}$ to about $2^{0.047n}$ ^{[17, 8]}, an erosion near 15 to 20 percent of the constant, and the running time never left the family $2^{\Theta(n)}$. The nearest-neighbor step that powers May-Ozerov is the same primitive that powers lattice sieving. Shared tooling, not shared hardness: a faster nearest-neighbor routine helps both cost estimates without linking the two assumptions ^[8]. Worse for the attacker, every post-Stern variant buys its lower time exponent with exponential memory, and the real cost of touching that much memory blunts the advantage.

// Two ISD exponents in one (half-distance) convention.
const cPrange = 0.057;   // Prange, 1962
const cModern = 0.0473;  // May-Ozerov regime, 2015

for (const n of [3488, 6688, 8192]) {
const bitsOld = cPrange * n;
const bitsNew = cModern * n;
console.log("n=" + n +
  "  Prange ~ 2^" + bitsOld.toFixed(0) +
  "   modern ~ 2^" + bitsNew.toFixed(0) +
  "   gap = " + (bitsOld - bitsNew).toFixed(0) + " bits");
}
// The exponent shrinks, but the problem stays firmly exponential.

Information-set decoding erodes margins; it does not collapse the problem. Fifty-six years of the sharpest attacks moved the exponent constant by roughly 15 to 20 percent and never once changed its exponential form. That is why a code-based parameter set ages slowly and predictably rather than failing overnight.

Real, but incremental. So if ISD only ever crawls, has it actually broken anything? Yes, once, decisively, and the receipt is the single most important fact in this article.

7. The Break ISD Already Delivered#

In 2008, Daniel Bernstein, Tanja Lange, and Christiane Peters did what thirty years of theory had implied but no one had cashed: they recovered plaintexts from McEliece's original parameters, the $[1024, 524]$ Goppa code with $t = 50$, at roughly $2^{60}$ operations on real hardware ^[22]. They also wrote down the prescription for restoring security: grow $n$, $k$, and $t$. Nothing more exotic was required.

This is the receipt, and it must be read precisely, because it is the fact most often garbled. What fell was the parameter set, the specific numbers McEliece chose in 1978. What did not fall was the binary-Goppa structure. The Bernstein-Lange-Peters attack never recovered the secret code; it decoded the public code generically, exactly as Prange would have, only faster. The trapdoor was never lifted.

So the familiar phrase "unbroken since 1978" is true, but only at the level of the structure and the assumption. At the level of the original numbers, ISD won in 2008, and the field had already moved to larger parameters by then.

Just how slowly does the ruler move? The Classic McEliece team runs CryptAttackTester, a computer-checked attack-cost tool, and publishes the bit-operation cost of 1980s-era ISD against current ISD on the same code sizes ^{[9, 23]}. The numbers are almost comically flat.

Four decades of the world's best ISD research removed about eighteen bits from a 275-bit problem ^[9]. That is real, and it is a rounding error against the security margin.

The units matter here. McEliece's 1978 paper estimated about $2^{65}$ bit operations for $(1024, 50)$, an underestimate even of the attacks known then, and improved ISD still needs more than $2^{65}$ bit operations. The fastest software today breaks $(1024, 50)$ in about $2^{60}$ CPU cycles, each cycle doing many bit operations at once -- the practical Bernstein-Lange-Peters message recovery ^[9]. The $2^{60}$ figure is a coarser unit, not a contradiction of the $2^{65}$ one. This is the thesis made concrete: ISD, not a structural break, has actually moved McEliece's numbers, and it moves them at a glacial pace.

So Door 1 erodes; it does not collapse. That should be reassuring, unless the disguise itself, the very thing that makes the public code look random, is quietly leaking. That is Door 2, and it just had its most dramatic decade in forty-seven years.

8. The Other Surface: Structural Distinguishers#

Every McEliece scheme rests on one bet: that a disguised algebraic code is indistinguishable from a random one. History says that bet is broken more often than it is kept, and the wreckage is instructive.

For thirty years the answer was reassuring. Then the structural front reawakened, each result escaping the previous one's limit and each reading the same suspicion in a different algebraic language: does the disguise leak a low-degree-polynomial fingerprint?

The high-rate distinguisher of Faugere, Gauthier-Umana, Otmani, Perret, and Tillich (2013) measures the dimension of a solution space built from the public code ^{[28, 29]}. The accessible restatement is the square-code, or Schur-product, test: square a code by taking all componentwise products of its codewords, and a random code fills the available dimension, while an alternant or Goppa code collapses into an abnormally small square-code dimension. That collapse is measurable only as the rate approaches 1, safely outside the moderate rate Classic McEliece deliberately fixes, which turns the moderate-rate choice from an efficiency compromise into an active defense.

The quadratic-forms approach of Couvreur, Mora, and Tillich (2023) escapes the rate-to-1 limit ^[30]. It builds the whole space of quadratic relations satisfied by Schur products of dual codewords and hunts for "unusually low-rank matrices (rank 2 or 3 ...) which reveal the secret polynomial structure of the code."

The mechanism is sharp: a rank-2 quadratic form factors as a product of two linear forms, and those linear forms encode the secret support and multipliers, so finding one low-rank matrix is extracting a piece of the key. That yields a subexponential distinguisher across a broad range, but its polynomial-time key recovery is confined to codes whose Goppa degree is small, below $q-1$, the high-rate, small-degree families Classic McEliece does not use.

Then the syzygy distinguisher of Randriambololona (2024) reads "graded Betti numbers of the homogeneous coordinate ring of a shortening of the dual code" ^[31]. Syzygies are the relations among the code's defining equations, and the relations among those relations; the graded Betti numbers count them degree by degree and so measure how algebraically regular the construction is.

Because a Goppa code comes from evaluating low-degree polynomials at a hidden support, its coordinate ring is unusually regular and its Betti numbers deviate from the random pattern. The computation is subexponential in the error-correcting capability $t$ rather than exponential, and, uniquely, it carries no high-rate restriction, so for the first time it reaches the parameters Classic McEliece actually ships.

Line the three up and the pattern is exact. All three ask whether the disguise leaks a low-degree-polynomial fingerprint. The 2013 test counts a dimension and leaks only at high rate; the 2023 test hunts a rank-2 matrix and leaks the secret itself, but in polynomial time only when the degree is below $q-1$; the 2024 test reads syzygies and leaks at McEliece's own rate, subexponentially in $t$. Each escaped the previous limit, and yet not one has turned its leak into key recovery at a deployed parameter set.

flowchart TD
A["2013 high-rate distinguisher"] --> A2["Bites only as the rate approaches 1, outside McEliece's moderate rate"]
A2 --> B["2023 quadratic-forms distinguisher"]
B --> B2["Subexponential over a broad range, with poly-time key recovery only for small-degree high-rate codes McEliece avoids"]
B2 --> C["2024 syzygy distinguisher"]
C --> C2["Subexponential, reaches Classic McEliece parameters, yet still only a distinguisher"]

"Since its introduction in 1978, this is the first time an analysis [in the CPA model] of the McEliece cryptosystem breaks the exponential barrier." -- Hugues Randriambololona, "The syzygy distinguisher" ^[31]

That sentence is doing careful work, and it is the aha of this section: the real existential threat to McEliece was never decoding the message. It is the disguise slipping. And the disguise, for the first time in forty-seven years, is showing a seam. But read the boundary exactly.

A warning light, then, not a fire, but the brightest warning light in forty-seven years. With both doors mapped, we can finally look at the two schemes that actually walked through standardization, and see how each is engineered against exactly these threats.

9. Classic McEliece: Conservative by Design#

Some engineers optimize for elegance. The Classic McEliece team optimized for one thing: being boring for as long as possible. The scheme is Niederreiter's syndrome form instantiated with binary Goppa codes, wrapped into an IND-CCA2 key-encapsulation mechanism by a tight Fujisaki-Okamoto conversion of a one-way PKE. Because the underlying encryption is deterministic and has no decryption failures for valid ciphertexts, that conversion admits a tight security reduction in both the classical and quantum random-oracle models ^[3].

Look at the design through the two doors. Against Door 2, the team fixes a deliberately moderate rate, sitting well away from the high-rate regime where the 2013 distinguisher operates. Against a whole class of adaptive attacks, the deterministic, failure-free decryption removes the decoding-failure channel entirely, so there is nothing to observe. And against Door 1, the parameters are chosen with what can only be called overkill. The price for all of this is paid in one currency: public-key size.

Public keys run from about 261 KB to about 1.36 MB ^[32]. That is the number everyone remembers, and it is a genuine deployment problem. But notice the other column, the one nobody talks about: the ciphertexts are 96 to 208 bytes ^[32]. A mceliece6688128 ciphertext is 208 bytes, smaller than ML-KEM-512's 768-byte ciphertext, while resting on a far longer-studied assumption. For a system that fetches a static public key once and then encapsulates to it many times, that trade is not obviously bad; it is merely unusual.

A megabyte key is a hard sell for an ephemeral TLS handshake, where a fresh key ships on every connection. That single ergonomic fact is why NIST reached instead for a scheme with kilobyte keys, and, along the way, a different and younger set of assumptions.

10. HQC: Quasi-Cyclic and NIST-Selected#

HQC makes the opposite bet from McEliece at almost every turn, and that is precisely why NIST picked it. Where McEliece hides a decodable code and keeps the decoder secret, HQC does the reverse.

Its hardness comes from decoding a random quasi-cyclic code, the quasi-cyclic syndrome-decoding problem, while error correction is handled by a separate, public, fixed decoder built from concatenated Reed-Muller and Reed-Solomon codes ^{[35, 36]}. Nothing about the decoder is secret; the only secret is the noise. The compactness comes from the cyclic structure: one block-row describes an entire circulant block, so the public key is kilobytes rather than megabytes.

The trade-off against McEliece is exact and opposite ^[37]. HQC's public keys are about 2 to 7 KB, against McEliece's 0.26 to 1.36 MB, but its ciphertexts are about 4 to 14 KB, against McEliece's 96 to 208 bytes. Small keys, larger ciphertexts. That shape suits ephemeral, per-session handshakes where a fresh public key ships every time.

The quasi-cyclic structure is not free, and honesty requires naming the surcharge. It is an added assumption beyond plain syndrome decoding, and it hands the attacker a specific speedup. DOOM, "Decoding One Out of Many," lets an attacker amortize one decoding across the many cyclic shifts of a quasi-cyclic instance, a speedup of roughly $\sqrt{N}$. It applies to HQC and BIKE and is already priced into their parameters; Classic McEliece, with no cyclic structure, does not pay it ^[38]. Both effects are quantified and folded into HQC's parameter choices.

How much security does that structure actually buy, and how do we know? Here HQC and McEliece part company in a way worth stating plainly. The 2025 HQC specification fixes its parameters "so that the minimal workfactor of the best known attack exceeds the security parameter," which is to say HQC-1, HQC-3, and HQC-5 are built to clear $2^{128}$, $2^{192}$, and $2^{256}$ classical operations by construction rather than by a printed per-instance count ^[39].

That workfactor is the cost of the best information-set decoder on the quasi-cyclic problem, of order $2^{c\omega}$ in the error weight $\omega$, divided by the DOOM gain of "approximately $\sqrt{n}$" -- about 7.0, 7.6, and 7.9 bits at HQC's three block sizes -- and then halved in the exponent for the quantum setting, since "the quantum-safe security is obtained by dividing the security bits by two," the same Grover discount McEliece applies ^{[39, 13]}.

An honest asymmetry hides in that sentence. McEliece quotes a computer-checked number: CryptAttackTester's isd2 gives $2^{150.59}$ at $(3488, 64)$ and $2^{257.36}$ at $(6688, 128)$ ^[9]. HQC quotes a target plus an asymptotic formula minus two discounts. No CAT-grade, fully computer-checked concrete count for quasi-cyclic syndrome decoding is published on the same footing, so the widely repeated third-party figures of roughly 145, 194, and 243 bits should not be attributed to the specification. They are estimator output, not a spec claim, and section 12 files the gap as an open problem.

Why HQC and not its sibling BIKE? Both are quasi-cyclic and both were candidates, but BIKE keeps its QC-MDPC decoder secret, and a hidden decoder has a key-correlated decoding-failure rate that is genuinely hard to analyze. The mathematical difficulty of pinning that failure rate, the design concern underlying the Guo-Johansson-Stankovski reaction-attack line, weighed against BIKE ^[40].

HQC's public decoder makes the same failure analysis far cleaner, and NIST's IR 8545 records this as a deciding factor, along with the reasons Classic McEliece was set aside ^[34]. HQC was announced in March 2025 as the second standardized KEM after ML-KEM, with a draft released for public comment first and the finalized standard expected in roughly two years ^[1], the outcome of a multi-year public process ^[41].

Two schemes, two unrelated hard problems, both standing. But there is one adversary the entire post-quantum project was built to survive. Does it touch either of them?

11. Quantum Cryptanalysis: Why Shor Misses#

The whole reason we are re-standardizing encryption is a quantum algorithm. So why does that same algorithm do nothing here? The answer is the most reassuring structural result in this article, and it is a positive one for the defender.

Shor's algorithm is not a general-purpose code breaker. It efficiently solves one abstract problem, and factoring and discrete logarithm happen to be instances of it.

That is the whole story of Shor against codes. General syndrome decoding presents no periodicity, no abelian hidden subgroup, no algebraic handle of the kind Shor's period-finding needs. There is no known efficient quantum algorithm for decoding a random linear code ^[13]. The property that made McEliece impractical in 1978, its refusal to reduce to clean number theory, is exactly the property that makes it quantum-safe in 2025.

Grover's algorithm does apply, but only to the search step inside ISD, and even there it underdelivers. Because ISD is not one big unstructured search, Grover speeds up only its innermost search, so the true quantum speedup is less than a full square root ^[13]. Schemes still set their quantum parameters by the deliberately conservative rule of halving the classical bit-security -- turning an attack near $2^{cn}$ into a budget of about $2^{(c/2)n}$ -- which upper-bounds Grover's real benefit rather than measuring it.

The countermeasure is generic and boring: increase the key size until the halved exponent is large enough again. The mceliece6* and HQC-5 tiers already fold this discount into their parameters, chosen "for long-term security, including security against multi-target attacks and against quantum attacks" ^[9]. A search discount absorbed by a parameter bump is a cost adjustment, not a structural break.

One symmetric corollary completes the hedge: just as a lattice break does not touch codes, a hypothetical quantum attack on lattices would not touch codes either. The two problems share no structure for such an attack to exploit. The independence runs in every direction.

So Shor misses, Grover only nibbles, and the hedge survives the one adversary it was built for. That is the strong half of the story. Now the honest, humbler half: what do we actually know about how hard these problems are?

12. Theoretical Limits and Open Problems#

Here is the uncomfortable truth under every code-based security claim, and it is the same truth under every deployed public-key system: we have never proven the problem is hard. We have only failed, for decades, to solve it. Naming exactly where the proof runs out is the honest security story, and it has three gaps.

The first gap is worst-case versus average-case. Decoding a general linear code is NP-complete ^[6], and that is the strongest worst-case anchor any scheme has. But Classic McEliece and HQC do not rest on the worst case. They rest on the average-case hardness of a specific structured family, binary Goppa or random quasi-cyclic, and no reduction connects the NP-complete worst case to that average case. An NP-hardness badge is not a security proof, and pretending otherwise is the most common overstatement in the whole subject.

The second gap is asymptotic versus concrete. Every ISD exponent is an asymptotic worst-case figure, and the concrete cost at a named parameter set depends on the memory model. ※ This is why the field increasingly trusts a computer-checked bit-operation count over a hand-analyzed asymptotic exponent. A variant with a lower time exponent but exponential memory may cost more in practice than its headline suggests.

That is why a computer-checked ruler like CryptAttackTester matters more than any single exponent ^{[9, 23]}, and it is why the one place HQC's ruler runs softer than McEliece's, a workfactor target and an asymptotic formula rather than a CAT-audited count for quasi-cyclic decoding, is worth flagging as an open item rather than waving through ^[39].

The third gap is distinguisher versus break, and the 2024 syzygy result lives exactly inside it: it distinguishes subexponentially, yet it does not recover ^[31]. A subexponential distinguisher that never becomes a recovery is a strange, in-between object, and reasoning about it demands the precision this whole article has insisted on.

Read against the thesis, the table is a weighed prediction, not a scoreboard. Door 1, better ISD, is likely but shallow: it will keep forcing periodic parameter growth, exactly as it did to the 1978 parameters, an erosion that never ends the family.

Door 2, a distinguisher maturing into key recovery, is unlikely but deep: it would end the family, and the frontier now reaches Classic McEliece parameters as a distinguisher while remaining short of a recovery. The most-likely fault line is continued ISD erosion; the most-dangerous fault line is the structural road; and neither has broken a deployed parameter set.

The most-likely break is shallow: continued ISD erosion, already seen once at the parameter level, which forces periodic parameter growth. The most-dangerous break is deep: a structural distinguisher maturing into key recovery, which would end the family. Neither has reached a deployed parameter set.

So we hold two believed-independent hard problems, two watched rulers, and no proofs. Given exactly that, how should you actually deploy the hedge today?

13. Deploying the Hedge Today#

The theory says "hedge." The engineering question is how, and the answer is not "pick one."

Choose Classic McEliece when you want the most conservative option on the table: a forty-seven-year track record, byte-sized ciphertexts, and a design with no decryption failures. Its megabyte public key is tolerable precisely when a static long-term key is fetched or pinned once and reused across many encapsulations, which is also the setting most exposed to harvest-now-decrypt-later collection ^[32].

Choose HQC when you want the NIST-selected KEM, balanced kilobyte-scale keys and ciphertexts, and general-purpose ergonomics that suit ephemeral, per-session handshakes where a fresh public key ships every time ^[37]. Classic McEliece is a poor fit there: shipping a fresh quarter-to-1.36-megabyte key on every session is prohibitive, the same key-size objection that kept it out of the NIST selection ^[34]. The deciding factor is usually bandwidth shape, not a single bit count.

But the real recommendation is neither scheme alone. It is to deploy in hybrid, and the combiner has a precise, provable shape. Run two independent KEMs and fold both shared secrets into one session key, so that breaking either component alone leaves the session key secure.

Giacon, Heuer, and Poettering proved that a black-box KEM combiner "yield[s] a new KEM that is (CCA) secure as long as at least one of the ingredient KEMs is," provided the key-derivation step also binds the component ciphertexts and public keys, the transcript ^[42]. That proviso is not a formality: a function that hashes only the two secrets and ignores the ciphertexts can lose IND-CCA security, because an attacker who mauls one component's ciphertext may leave the derived key unchanged, defeating non-malleability.

The concrete, IND-CCA-preserving instance is X-Wing, which fixes X25519 and ML-KEM-768 and sets the session key to SHA3-256(ss_ML-KEM || ss_X25519 || ct_X25519 || pk_X25519 || XWingLabel) ^{[43, 44]}. It is proved to be a post-quantum IND-CCA KEM if ML-KEM-768 is one, and a classically IND-CCA KEM if the strong Diffie-Hellman assumption holds for X25519: secure if either component survives ^[43]. Notice that it binds the X25519 ciphertext and public key directly but does not re-hash the ML-KEM ciphertext, because ML-KEM's own transform already folds that ciphertext into its shared secret ^[44].

Wire the two schemes of this article into that frame by matching NIST security levels. For long-term, harvest-now-sensitive static-key data, run a level-5 triple hedge, X25519 with ML-KEM-1024 and mceliece6688128 or mceliece8192128, so that no single break across classical, lattice, or code is fatal; McEliece belongs here specifically because a static key amortizes over many messages while its 208-byte ciphertexts dominate per-message traffic ^{[32, 34]}.

For ephemeral per-session handshakes, run X25519 with ML-KEM-768 or ML-KEM-1024 and HQC-3 or HQC-5, or take X-Wing as the baseline and add an HQC leg only where a code-based hedge is mandated ^[37]. That layered posture is the entire reason NIST standardized a code-based KEM after it already had a lattice one ^[34].

One boundary carries over from the very first section. Choosing a scheme, or a combiner, with a well-understood mathematical fault line does not exempt you from the implementation attacks that fill the companion track: constant-time decoding, protected randomness, and careful failure handling still matter. The combiner itself is a construction, in scope for this article; its constant-time, side-channel-resistant implementation is not. This article told you where the algorithm would give way. It did not promise your code was written correctly.

Deploying the hedge well means holding two ideas at once: real confidence in the independence of the bet, and clear eyes about its fault lines. The FAQ tackles the specific confusions that break that balance.

14. Frequently Asked Questions#

Every answer points back to one idea: precise language is the difference between "watched" and "broken."

15. The Hedge and Its Fault Line#

Return to March 2025. NIST, having already crowned a lattice-based encryption standard, standardized a second one on a bruised 1978 idea, and it looked like betting against its own decision. It was not. It was refusing to keep all of encryption's weight on a single hard problem.

Everything since has justified that refusal. Code-based cryptography is the diversification bet, and the bet is sound in the one way that matters: a lattice break does not debit it. Shor's algorithm structurally misses syndrome decoding, and no reduction connects the two assumptions, so the independence is real rather than rhetorical.

Its own most-likely fault line is not exotic. It is information-set decoding, which has already "broken" McEliece once, at the level of the 1978 parameters, never the structure, and which crawls, moving the security exponent only about 15 to 20 percent in fifty-six years ^[9]. Its deeper, less-likely fault line is a structural distinguisher maturing into key recovery, a frontier that in 2024 finally reached Classic McEliece parameters yet remains a distinguisher, not a break ^[31]. Both fault lines are watched closely. Neither has reached a recommended parameter set.

That is the shape of the whole argument, and it carries a lesson beyond these two schemes. The deepest security engineering is sometimes not building the strongest single wall. It is declining to bet everything on one wall, however strong, because the history of this field is a history of strong walls falling to a single new idea. Two believed-independent hard problems, each with a slowly-moving, well-instrumented ruler, is a sturdier posture than one problem with a taller number.

There is a quiet marvel in where this landed. An idea from 1978, dismissed for two decades as an impractical museum piece, too bulky to use, is now the insurance policy on the entire post-quantum transition. It did not have to become strong. It only had to stay different.