International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Higher-genus McEliece

Authors:
Daniel J. Bernstein , University of Illinois at Chicago and Academia Sinica
Tanja Lange , Eindhoven University of Technology
Alex Pellegrini , Eindhoven University of Technology
Download:
Search ePrint
Search Google
Conference: ASIACRYPT 2025
Abstract: The best attacks known against the McEliece cryptosystem have cost growing exponentially with the number of errors corrected by the error-correcting code used in the cryptosystem. One can modify the cryptosystem to asymptotically increase this number of errors, for the same key size and the same ciphertext size, by generalizing classical binary Goppa codes to subfield subcodes of algebraic-geometry codes, and then moving from genus 0 to higher genus. This paper introduces streamlined algorithms for code generation and decoding for a broad class of these codes; shows that this class includes classical binary Goppa codes; and shows that moving to higher genus within this class decodes more errors than classical binary Goppa codes for concrete sizes of cryptographic interest. A notable feature of this paper's algorithms is the use of arithmetic on the Jacobian variety of the underlying curve.
BibTeX
@inproceedings{asiacrypt-2025-36146,
  title={Higher-genus McEliece},
  publisher={Springer-Verlag},
  author={Daniel J. Bernstein and Tanja Lange and Alex Pellegrini},
  year=2025
}