Paper 2024/1193
The syzygy distinguisher
Abstract
We present a new distinguisher for alternant and Goppa codes, whose complexity is subexponential in the error-correcting capability, hence better than that of generic decoding algorithms. Moreover it does not suffer from the strong regime limitations of the previous distinguishers or structure recovery algorithms: in particular, it applies to the codes used in the Classic McEliece candidate for postquantum cryptography standardization. The invariants that allow us to distinguish are graded Betti numbers of the homogeneous coordinate ring of a shortening of the dual code. Since its introduction in 1978, this is the first time an analysis of the McEliece cryptosystem breaks the exponential barrier.
Note: Eurocrypt 2025 version, expanded, with supplementary material and errata
Metadata
- Available format(s)
-
PDF
- Category
- Attacks and cryptanalysis
- Publication info
- A major revision of an IACR publication in EUROCRYPT 2025
- DOI
- 10.1007/978-3-031-91095-1_12
- Contact author(s)
- hugues randriam @ ssi gouv fr
- History
- 2025-05-01: last of 3 revisions
- 2024-07-24: received
- See all versions
- Short URL
- https://ia.cr/2024/1193
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2024/1193,
author = {Hugues RANDRIAMBOLOLONA},
title = {The syzygy distinguisher},
howpublished = {Cryptology {ePrint} Archive, Paper 2024/1193},
year = {2024},
doi = {10.1007/978-3-031-91095-1_12},
url = {https://eprint.iacr.org/2024/1193}
}