Distinguishing Goppa codes using higher-order vanishing

Tobias Hemmert; Andreas Wiemers

Paper 2025/1661

Distinguishing Goppa codes using higher-order vanishing

Tobias Hemmert, Federal Office for Information Security

Andreas Wiemers

, Federal Office for Information Security

Abstract

We present a new algorithm to distinguish alternant and Goppa codes from general linear codes. Our approach is based on higher-order vanishing of polynomials and can be applied to a wide set of code parameters. It also applies to Goppa code parameters used in the Classic McEliece key encapsulation mechanism. While these parameters are out of reach in practice, we analyse the behaviour of our distinguisher and estimate its complexity for them, indicating that it is more efficient than previous distinguishing approaches. This is supported by concrete experiments that distinguish codes with larger parameters in practice.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Published by the IACR in CRYPTO 2026
Keywords: McEliece Goppa code distinguisher
Contact author(s): tobias hemmert @ bsi bund de
alter ego2048 @ googlemail com
History: 2026-06-29: last of 2 revisions; 2025-09-13: received; See all versions
Short URL: https://ia.cr/2025/1661
License: CC BY

BibTeX

@misc{cryptoeprint:2025/1661,
      author = {Tobias Hemmert and Andreas Wiemers},
      title = {Distinguishing Goppa codes using higher-order vanishing},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/1661},
      year = {2025},
      url = {https://eprint.iacr.org/2025/1661}
}