A New Classic McEliece Distinguisher Undercuts Generic Decoding. It Is Not a Break.

August 10, 2026 — Ashrujit Ghoshal (IIT Madras), Yuval Ishai (Technion and AWS), and Aayush Jain and Nuozhou Sun (Carnegie Mellon University) have posted a classical quasipolynomial-time distinguisher for the binary Goppa codes that underpin Classic McEliece, the code-based key encapsulation mechanism ISO added to its asymmetric-ciphers standard in June 2026. The paper, Quasipolynomial Cryptanalysis of the McEliece Cryptosystem (or: PIR Meets McEliece), was received by the IACR Cryptology ePrint Archive on August 7 and approved on August 10. It does not break the scheme.

The algorithm decides whether a matrix generates a Classic McEliece public code or a uniformly random binary code. Classic McEliece has never claimed those two are indistinguishable. Its underlying encryption primitive is analyzed for one-way security against chosen-plaintext attack, the KEM built on top targets IND-CCA2 through a tight conversion, and the team’s security analysis explicitly disclaims the public-key pseudorandomness this attack defeats.

For anyone tracking algorithm risk, the bottom line runs in two parts. No security claim has fallen. And under the authors’ cost model this is still the first published structural distinguisher whose estimated cost falls below the cited information-set-decoding figure for every Classic McEliece parameter set NIST considered, on a distinguishing argument that uses no heuristic assumptions. The two algorithms solve different problems: information-set decoding recovers a message, while the distinguisher only recognizes structure. Staying above the generic-decoding cost was nonetheless the quantitative argument that made structural attacks easy to set aside, and that argument is gone.

Mechanically, the distinguisher holds out one column, computes the space of multilinear homogeneous polynomials of degree $$d$$ whose Hasse derivatives of order below $$s$$ vanish at every remaining column, then checks whether those polynomials also vanish at the held-out column. For a Goppa key the answer is forced by Hermite interpolation. For a random matrix it fails with constant probability. A single hold-out gives only a constant distinguishing gap; holding out several independent columns amplifies that to $$1 – o(1)$$, at running time $$n^{O(\log n)}$$. Because Classic McEliece publishes a systematic parity-check matrix in Niederreiter form, the attack converts it to an equivalent scrambled generator matrix first.

Counted as binary operations in the Boolean-circuit model of Bernstein and Chou’s CryptAttackTester, the estimates run from 2¹¹⁴ for mceliece348864 to 2¹²⁴ for mceliece8192128. Information-set decoding against the same parameter sets is estimated at 2¹⁵¹ to 2²⁸⁷. The previous strongest concrete structural distinguisher, the higher-order-vanishing method of Tobias Hemmert and Andreas Wiemers and its key-recovery extension, was estimated at 2²⁹⁸ to 2⁶⁹¹ across the same five sets. Storage estimates run from 2^66.45 to 2^71.37 bits, about 13 to 380 exabytes, which the authors state they did not attempt to optimize.

Asymptotically, the result improves on Hugues Randriambololona’s syzygy distinguisher, which won a Best Paper award at Eurocrypt 2025 for the first subexponential structural analysis of Goppa–McEliece. Randriambololona’s complexity depends on a heuristic prediction for graded Betti numbers on random codes. So do the quadratic-relation approaches of Couvreur, Mora, and Tillich and the recent bilinear attack of Briaud, Lemoine, Randriambololona, and Tillich. The new distinguisher’s soundness follows from Schwartz–Zippel over extension fields and, in the binary case, from the minimum-distance bound for Reed–Muller codes.

The attack originated in a failed attempt to build doubly efficient private information retrieval from algebraic locally decodable codes. Ghoshal and his co-authors observed that a McEliece public key has the same algebraic shape as the query distribution of a natural PIR candidate, and that the span-based attack known to sink such PIR schemes converts into a distinguisher. Replacing the Reed–Muller encoding with an order-$$s$$ multiplicity code supplies $$s$$ Hermite-interpolation constraints per coordinate rather than one, which is what carries the technique past the rate-1/2 barrier that confines Schur-product distinguishers.

A second result extends the framework to ciphertext decryption. The ciphertext is appended to the public matrix as an extra row, the hold-out test is run at every coordinate to separate clean coordinates from those carrying error, and the message is recovered by linear algebra on the clean set. Acceptance of clean coordinates is proven. Rejection of dirty ones is not, and rests on genericity hypotheses supported by experiments on small Reed–Solomon, alternant, ordinary Goppa, and wild Goppa instances. The authors report binary-Goppa-specific partial experiments, including 1,800 dirty-coordinate rejection trials in which every dirty coordinate was rejected in 1,769. What they could not do is run the attack end to end on a binary Goppa instance meeting their parameter constraints, because the smallest compatible case requires solving a linear system of dimension roughly 2²⁷. They describe the concrete cost of the decryption attack as “far beyond practical reach.”

Classic McEliece is not a NIST standard. NIST advanced it to the fourth round and then selected HQC in March 2025 as its code-based backup key encapsulation mechanism, documenting the reasoning in NIST IR 8545. NIST did not question the scheme’s security. It cited the size of the public keys and limited evidence of deployment interest. HQC itself is selected rather than finalized; the standard has not been published. It reached international standardization through a different route: ISO/IEC 18033-2:2006/Amd 2:2026, published in June, which added ML-KEM, FrodoKEM, and Classic McEliece to the asymmetric-ciphers standard. Germany’s BSI has recommended it with suitable parameters and in hybrid deployment since TR-02102-1 version 2020-01, a position carried into the current 2026-01 revision. The Dutch PQC Migration Handbook from AIVD, CWI, and TNO recommends ML-KEM and rates Classic McEliece as acceptable, describing it as the more conservative and thoroughly studied option. In production, Mullvad has shipped it by default on desktop since January 2025, paired with ML-KEM, and the Rosenpass project combines it with Kyber.

I found no response from the Classic McEliece team on its website or in the publicly indexed pqc-forum archive as of publication. The site’s intro page carries a version stamp of June 19, 2026.

My Analysis

Two waves of noise are coming and they point in opposite directions. The first has already started, because a paper titled “Quasipolynomial Cryptanalysis of the McEliece Cryptosystem” reads like a break to anyone who stops at the title, and plenty of people stop at the title. The second arrives when the Classic McEliece team responds, and it will say that distinguishers were never in scope and nothing here counts.

Both are wrong. The second will be wrong in the more interesting way, and it is the one I expect to hear from people who should know better.

Half of the standing defense just went away

Classic McEliece has been through this before. When Randriambololona’s syzygy distinguisher appeared in 2024, Daniel J. Bernstein replied on the NIST pqc-forum on behalf of the team with a two-part rebuttal. First, the conjectured costs exceeded information-set decoding for every proposed parameter set. Second, the target was only a distinguisher, and the indistinguishability assumption is not used in the Classic McEliece security analysis. It is disclaimed there. As Bernstein put it, “even a fast distinguisher wouldn’t violate the Classic McEliece security claims.”

The second half of that argument is untouched. The team designed for OW-CPA, states so on the front page of its own site, and built the KEM by a tight conversion from a one-way PKE. Public-key pseudorandomness is a property other people assumed, not one Classic McEliece promised. A distinguisher running in 2¹¹⁴ operations violates no claim the team has ever made, and anyone reporting this as a break should say which claim they think fell.

Its first half no longer holds. Ghoshal, Ishai, Jain, and Sun beat ISD by 2³⁷ on the smallest parameter set and by 2¹⁶³ on mceliece8192128. The quantitative argument that made distinguishers safe to set aside no longer describes the situation, and the next version of that argument will have to be built on the OW-CPA distinction alone.

Proof-based is not the same as proven

Concrete cost estimates get revised. Heuristics get refuted. The IACR ePrint archive is full of attack papers whose numbers moved after a week on a mailing list, and the Classic McEliece team maintains a dedicated page rebutting a 2025 distinguisher claim, so the machinery for that is already warm.

Proofs in new preprints get revised too, as the Simon paper three paragraphs from now demonstrates at some length. What separates this result is not immunity from review but the absence of the conjectural scaffolding every prior Classic-regime distinguisher carried. Randriambololona needs a prediction about Betti numbers of random codes. Hemmert and Wiemers need their vanishing space to be trivial on random inputs. Briaud and co-authors need assumptions about matrix ranks. Ghoshal and his co-authors need Hasse derivatives, a tool from 1936, Hermite interpolation, a formula from 1878, and the minimum distance of Reed–Muller codes, established in 1954. That is a materially firmer footing. It is not a certificate.

The decryption attack is a different animal, and I would resist any framing that blurs them. Its rejection step is heuristic, no end-to-end binary Goppa run exists, and the authors say plainly that it should be read as an asymptotic proof of concept. If it holds, they argue, Classic McEliece would stand apart from the other standardized public-key families in having a known quasipolynomial decryption algorithm. That is an absence-of-known-attack claim about everyone else, resting on hypotheses tested at small instance sizes. The authors flagged it as an open problem, and that is how it should be read until someone runs it.

The exabyte problem

Before anyone builds a risk register entry around 2¹¹⁴, look at the storage column. The attack needs 2^66.45 to 2^71.37 bits of working memory, which is somewhere between thirteen and three hundred eighty exabytes, and the authors are candid that they never optimized it. The Boolean-circuit cost model they use counts arbitrary two-input gates at unit cost, treats fan-out as free, and ignores depth, layout, and communication, which the authors describe as an optimistic operation count rather than an implementation cost.

None of that makes 2¹¹⁴ uninteresting. It makes it a research milestone with no plausible implementation path on current architectures, in a model that excludes precisely the data movement an exabyte-scale sparse solve would be dominated by. The mceliece348864 parameter set targets NIST Category 1, and a structural attack priced below the generic-decoding estimate at that level is exactly the signal a conservative design is supposed to keep clear of. What eroded here is design margin, not operational security.

ISO standardized this just over two months ago

Jurisdiction does more work in this story than mathematics does, though not in the tidy shape a headline would like.

NIST selected HQC as its additional code-based KEM and declined to standardize Classic McEliece. ISO/IEC, which is an international body rather than a European one, later added Classic McEliece to 18033-2 alongside ML-KEM and FrodoKEM, with no comparable selection contest. Separately, BSI has recommended Classic McEliece since 2020 and reaffirmed that in January, and the Dutch agencies rate it acceptable and conservative. Those are three different kinds of decision, and flattening them into a transatlantic split would be the easy version of a more interesting problem. The point that survives is the one I argue in Quantum Sovereignty: when jurisdictions land on different algorithms for different reasons, they take on different cryptanalytic exposure, and the exposure arrives on nobody’s schedule.

Hybrid deployment limits the damage, but not every hybrid limits it the same way, and I want to be careful here because I argued the general version of this point last week and would rather not contradict myself in public.

The classical-plus-PQC hybrids that BSI and ANSSI mandate do work against this particular event, because this attack is classical. An adversary who broke Classic McEliece outright tomorrow still faces an intact X25519 layer, and no quantum computer exists to remove it. That is a real protection and it is available today.

What it does not protect is traffic being harvested now. HNDL exposure needs both layers to survive until the day someone tries to decrypt, and on that day the classical layer is gone by assumption. Mullvad’s construction is the one that answers this properly, because Classic McEliece and ML-KEM are two post-quantum families and a structural break in one leaves the other standing. Cross-family post-quantum is the durable hedge. Classical-plus-PQC buys time.

On July 15, a press release from Post-Quantum Ltd announcing the ISO standardization called Classic McEliece “the most secure PQC algorithm available”, on the authority of the cryptographic community. Twenty-three days later, four researchers posted the first attack on it that costs less than generic decoding. Cryptography rewards a certain kind of humility, and marketing copy has never been where you find it.

I would still like to know how many procurement decisions in the past two months cited the ISO designation as evidence of superior security. That framing was doing real work in the market, and it should stop now.

One week, two branches, different weather

Last week I argued, in my analysis of Daniel Simon’s dihedral coset paper that the meaningful hedge in post-quantum migration is diversity of mathematical family rather than classical-plus-lattice hybrid, because an adversary with the hardware to run a lattice attack also has the hardware to run Shor’s algorithm. Code-based plus lattice is a real hedge. Classical plus lattice is a transitional one.

Four days after that piece, the code-based branch takes a hit. I am not going to pretend that is comfortable, but I am also not going to overread it.

The two events are not the same kind of event, and the asymmetry runs opposite to the news cycle. Simon’s claim is a quantum algorithm with two confirmed proof gaps, in Lemmas 3 and 4, which the verification group is treating as an insufficient proof rather than a failed algorithm. This McEliece distinguisher is classical, carries no heuristic on its distinguishing side, and needs no quantum computer. The louder story is still waiting on a repair. The quieter one is waiting only on review.

More importantly, “code-based” is not one thing. This attack works by detecting hidden algebraic structure, specifically a public code sitting inside an ambient generalized Reed–Solomon code over an extension field. That framework reaches Goppa, alternant, wild Goppa, and plausibly algebraic-geometry codes. HQC’s security does not rest on hiding an algebraic structure; it rests on the difficulty of decoding random quasi-cyclic codes, with the decoding machinery public. NIST’s code-based backup falls outside the scope of this attack framework, which is not the same as immunity from structural cryptanalysis generally. Neither is SLH-DSA, which is hash-based and structurally unrelated to all of it.

The lesson is narrower and more useful than “diversification failed.” Diversification reduces correlated failure. It does not reduce per-branch risk, and it only pays out if each branch is actually swappable in your architecture.

Which brings me to the awkward part. Diversification is easy to recommend and getting harder to carry out. The key-establishment menu has four entries: ML-KEM on module lattices, FrodoKEM on plain LWE, Classic McEliece on binary Goppa codes, and HQC on quasi-cyclic codes. Inside seven days the first drew a contested quantum claim, the second turned out to sit closest to that claim’s own corollary, and the third acquired this. HQC is the one branch nobody has laid a glove on, and it is selected rather than standardized, with no published FIPS to build against until 2027.

So the advice that holds is not “choose safer algorithms.” Nobody can tell you which those are this month. It is that the cost of changing your mind should be low enough that you can afford to be wrong about the choice you made. That is crypto-agility, and I have now argued it three times in two weeks from three unrelated directions: an AI security incident, a quantum claim against lattices, and a classical attack on codes. None of the three had anything to do with when a quantum computer arrives. Crypto-agility is not a Q-Day hedge. It is a hedge against mathematics, which moves on its own schedule and has moved twice this month.

What this changes for a migration program

Nothing this week.

Do not remove Classic McEliece from a hybrid deployment. Removing the code-based component of a hybrid construction over a distinguisher that violates no security claim would be a worse decision than the one that put it there.

Do check whether Classic McEliece appears anywhere in your estate as a sole KEM rather than a hybrid component. It is rare, but the PQC Migration Framework discovery phase exists to answer questions like this in hours instead of quarters, and this is the week to run the query.

Do record the event. A cryptographic registry that cannot answer “which systems depend on binary Goppa hardness” is not a registry, and algorithm-risk events are exactly what the review-date field is for.

Do write down which mathematical family each key-establishment path depends on. Not which vendor or which product: which family. If every path in your estate resolves to “lattice,” or every path resolves to “code-based,” you hold a concentration risk that no amount of supplier diversity touches. Two of the four available families took hits in the past seven days, which makes that inventory question considerably less theoretical than it was in July.

Do watch the pqc-forum. A response is likely, it will be technically substantive, and it may materially revise the concrete comparison. Prior rounds of this argument produced real corrections in both directions, and the team maintains a standing rebuttal page for exactly this purpose.

Do not attach this to Q-Day or the CRQC timeline. This is classical cryptanalysis. It moves nothing on the hardware curve, and anyone bolting quantum framing onto it is telling you they did not read past the abstract. The version of this argument that does bear on timelines runs through the deadlines regulators, insurers, investors, and clients have already set, which were never contingent on a Q-Day prediction anyway.

A footnote on how this was verified

The AI disclosure at the end of the paper deserves reading. Ghoshal and his co-authors state that the main results came out of the failed PIR attempt through human trial and error without AI, and then list what AI did do: OpenAI Codex verified the results, analyzed and improved the concrete efficiency, drafted some of the proofs, coded the experiments behind the decryption heuristic, and helped with the literature review. Amazon Quick and a Google harness performed additional sanity checks. The acknowledgments thank both David Woodruff and Google’s internal AI harness in the same sentence.

I disclose AI assistance in my own workflow, so I am not raising an eyebrow at theirs. My point is narrower. The concrete efficiency analysis is the part of this paper most likely to be contested, and it is also the part where the authors credit machine assistance most directly. The community is about to litigate a set of numbers partly produced by tooling that most of the reviewers have not run. I have no idea yet how that changes the shape of a cryptanalytic argument. We are going to find out.

Nearly five decades of cryptanalysis have not produced a practical decryption or key-recovery break of the submitted Classic McEliece parameter sets. This week did not either. What thinned is the margin around public-key pseudorandomness and resistance to structural recognition, a property the scheme never promised but one that carried much of its reputation as the conservative choice. The organizations that picked it for that reputation should record the change and keep their hybrids.