Thirty Bits of Maybe
A drawing of a sparse grid. Not a Classic McEliece public key, and not anyone’s linear-algebra run.
Classic McEliece is a public-key scheme from 1978 that never quite left the room. Robert McEliece hid a binary Goppa code behind a scrambled generator matrix. Harald Niederreiter’s dual version publishes a scrambled parity-check matrix instead. The modern thing is a Niederreiter-style key-encapsulation mechanism. NIST kept it through a fourth round and did not select it. ISO/IEC standardised selected parameter sets in June 2026 and left the smallest one, mceliece348864, out. The German BSI had recommended the scheme since 2020.
The structure was supposed to stay hidden
Security sat on two claims. Decoding a random linear code is hard: information-set decoding, in the line of Prange, has only crept forward in sixty years. And nobody could cheaply recognise the hidden Goppa code. Before this wave, the BSI put the best key recovery above 2 to the 3000 operations, even on the smallest set, using Sendrier’s support-splitting search. So the published sizes were chosen against generic decoding, not against someone who unmasks the code.
A distinguisher is not a break. It says “this matrix is not a random code.” It does not hand you a decoder. A key recovery has to build some equivalent secret: a support and a Goppa polynomial that define the same public code. Recovering one small challenge is not a cost for the real sizes. Fernandez keeps those three apart on purpose. I am keeping them apart too.
Two years, then a memo
The paper is arXiv:2610.31196, Ramses Fernandez, submitted 22 October 2026. It is an assessment, not a new attack. From 2024 the structural results moved faster than in the previous four decades. Randriambololona’s syzygy distinguisher. Higher-order vanishing. A quasi-polynomial Holdout/Hermite distinguisher by Ghoshal, Ishai, Jain, and Sun. Then key-recovery algorithms built on that distinguisher, including Saarinen’s HOVER and his recovery of a challenge labeled TII-254, and Weis’s cost study of the same linear algebra.
The labels on those challenges are brute-force work-factor estimates. They are not security levels. The highest solved label in the abstract is 254. The lowest published estimates for the real Classic McEliece sets are conditional: about 2 to the 89 through 2 to the 128 per run of one large sparse linear-algebra computation. The spread depends on the parameter set and on whether memory access is charged.
On 29 September 2026 the BSI advised against new deployments. The same note, as Fernandez reads it, says the published results do not yet enable a practical attack on the parameter sets the office had recommended. “Advised against” and “not yet practical” are both in that sentence. I am not collapsing them.
The bill depends on how you count memory
Fernandez’s own reading is that the cost model is now the main quantitative uncertainty. For the same computation, the cheapest model and the most expensive model sit about thirty bits apart. NIST’s category 1, 3, and 5 reference levels, counted as gates for AES key search, are 2 to the 143, 2 to the 207, and 2 to the 272. For the four larger parameter sets, every model he considers leaves the conditional estimates far below those targets. For mceliece348864 the shortfall is about as wide as the disagreement between models. Those structural estimates also sit under Grover-accelerated information-set decoding for the four larger sets, in essentially every model, and are comparable for the small one.
None of that is a demonstrated attack on a real key. The heuristics have been tried on instances tens of thousands to hundreds of thousands of times smaller than the target. A conditional 2 to the 89 is a model of a computation nobody has run at full size. The old 2 to the 3000 was also a model. They are not two measurements of the same machine.
| Set | n | t | NIST category | Public key |
|---|---|---|---|---|
| mceliece348864 | 3488 | 64 | 1 | 261,120 bytes |
| mceliece460896 | 4608 | 96 | 3 | 524,160 bytes |
| mceliece6688128 | 6688 | 128 | 5 | 1,044,992 bytes |
| mceliece6960119 | 6960 | 119 | 5 | 1,047,319 bytes |
| mceliece8192128 | 8192 | 128 | 5 | 1,357,824 bytes |
Table 1 of the paper, the five fourth-round sets. The public key is the non-identity part of a systematic parity-check matrix. ISO/IEC’s June 2026 amendment standardises selected sets and excludes the first row.
The distinguisher removed an assumption. The cost model moved the bill by about thirty bits. The full-size key is still a computation, not a broken lock.
Source: arXiv:2610.31196, v1, 22 October 2026, Ramses Fernandez. The 2^89 to 2^128 window, the about-thirty-bit cost-model spread, the TII labels up to 254, the BSI advice of 29 September 2026 against new deployments together with the statement that this is not yet a practical attack, the pre-2024 figure above 2^3000, NIST gate levels 2^143, 2^207, and 2^272, Table 1’s five parameter sets, the ISO/IEC standardisation in June 2026 that excludes mceliece348864, and the warning that the heuristics were tested on instances tens of thousands to hundreds of thousands of times smaller than the target. The slider is a cartoon of that thirty-bit sentence. It is not a reproduction of Weis’s per-parameter table, and the grey bar is not drawn at 3000.