Paper 2026/1339
Key recovery for the McEliece cryptosystem using higher-order vanishing
Abstract
We present a new key recovery attack against the McEliece cryptosystem with binary Goppa codes that applies to a wide range of parameter sets. Earlier work already observed that homogeneous polynomials vanishing of higher order at the columns of the parity check matrix of a given code could be used to distinguish binary Goppa codes from random linear codes. This work now exploits the structure of these polynomials for key recovery. We illustrate the effectiveness of our approach by breaking a number of previously unbroken McEliece key recovery challenges published by the Technology Innovation Institute (TII). We conjecture that our approach also applies to Classic McEliece parameter sets and yields a key recovery algorithm with roughly the same complexity as the higher-order vanishing distinguisher. While this complexity is still significantly higher than the targeted security level of Classic McEliece parameter sets, this improves on currently known key recovery attacks.
Metadata
- Available format(s)
-
PDF
- Category
- Public-key cryptography
- Publication info
- Preprint.
- Keywords
- McEliecekey recoveryTII challengesGoppa codes
- Contact author(s)
- tobias hemmert @ bsi bund de
- History
- 2026-07-02: approved
- 2026-06-29: received
- See all versions
- Short URL
- https://ia.cr/2026/1339
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2026/1339,
author = {Tobias Hemmert},
title = {Key recovery for the {McEliece} cryptosystem using higher-order vanishing},
howpublished = {Cryptology {ePrint} Archive, Paper 2026/1339},
year = {2026},
url = {https://eprint.iacr.org/2026/1339}
}
