Paper reassesses structural attack claims against Classic McEliece
Original title: Structural cryptanalysis of classic McEliece: Assessment of claims, costs and evidence
Conditional recovery estimates fall well below targets for larger sets, but the authors say no attack is demonstrated.
The paper reviews two years of structural attacks on Classic McEliece with binary Goppa codes, including distinguishers, challenge recoveries with brute-force labels up to 254, and conditional cost estimates of about 2^89 to 2^128. It finds the cost model is the main uncertainty, with about thirty bits between models, and that estimates for the four larger parameter sets stay far below targeted levels in every model considered. Heuristics were tested only on instances tens of thousands to hundreds of thousands of times smaller than the targets. In September 2026 the German BSI advised against new deployments.
Unconfirmed: Cost figures are conditional estimates, and the underlying heuristics have not been tested at target size.
- Saarinen's recovery of the TII-254 challenge and the HOVER cost analysis are reviewed in detail.
- For mceliece348864 the shortfall is about the spread between cost models.
- Structural estimates are lower than Grover-accelerated information-set decoding for the four larger sets in essentially every model.
- The authors say none of the results is a demonstrated attack on the target parameters.
- Products
- Classic McEliecemceliece348864
- Organizations
- BSI
- Countries
- Germany
From the original article
1 min read at arxiv.orgFor the last two years, classical structural attacks on McEliece with binary Goppa codes progressed further, at the parameters of Classic McEliece, than in the previous four decades: a subexponential and then a quasi-polynomial distinguisher, key recoveries for public challenges with brute-force labels up to $254$, and conditional key-recovery estimates of about $2^{89}$ to $2^{128}$ per run of a large sparse…
By Ramses Fernandez · arxiv.org
A short excerpt; the article and its images belong to the publisher. Summary, key facts and assessment above are AI-written from the article and can be wrong.