Newest papers

Structural cryptanalysis of classic McEliece: Assessment of claims, costs and evidence

Ramses Fernandez · 2026 · arXiv (Cornell University)

DOI: 10.48550/arxiv.2610.31196 · cited by 0 works (OpenAlex) · open-access PDF

German

Für die letzten vier Jahre ist der Holon-Parameter-Angriff niedriger strukturiert, da klassische zielgerichtete Angriffe auf McEliece mit binären Goppa-Codes auf den Parametern von Classic McEliece weiter vorangegangen sind als in den vergangenen vier Jahrzehnten: ein gleichartiger subexponentieller und dann ein quasi-polynomischer Hauptdifferenzierender, Schlüsselwiederherstellung für öffentliche Herausforderungen mit Brutto-Kraft-Etiketten bis zu $254$, und bedingte Schlüsselwiederherstellungs-Schätzungen von etwa $2^{89}$ bis $2^{128}$ pro Lauf einer großen sparsamen linearen Algebra-Berechnung, abhängig vom Parameter-Set und darüber, ob und wie der Zugang

Machine translation (Meta M2M100); the English original follows.

Abstract

For 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 linear-algebra computation, depending on the parameter set and on whether and how memory access is charged. On September 2026 the German BSI advised against new deployments of the scheme. This paper gives a version-aware critical assessment of these results. It separates proved distinguishers, conditional cost estimates and actual recoveries; analyses in detail Saarinen's HOVER algorithm, his conditional cost analysis and his recovery of the TII-254 challenge, together with Weis's cost study of Holdout/Hermite key recovery; and compares the other key-recovery routes and the objections raised against them. Our own analysis finds that the cost model is now the main quantitative uncertainty, with about thirty bits between the cheapest and the most expensive model for the same computation; that for the four larger parameter sets every model considered leaves the conditional estimates far below the targeted levels, whereas for mceliece348864 the shortfall is of the order of the spread between models; that the structural estimates are lower than Grover-accelerated information-set decoding for the four larger sets in essentially every model and comparable for mceliece348864; and that none of this is a demonstrated attack, since the underlying heuristics have been tested only on instances tens of thousands to hundreds of thousands of times smaller than the target. We close with open questions.

Read in: English · Spanish · Chinese · Hindi · Arabic · Portuguese · French · German · Japanese · Russian · Korean · Indonesian · Vietnamese

Topics: McEliece cryptosystem, Heuristics, Set (abstract data type), Cryptanalysis, Key (lock), Computer science

Sources: OpenAlex (CC0), arXiv, Crossref. Agent Exchange