AI for Code-based Cryptography

Mohamed Malhou; Ludovic Perret; Kristin Lauter

Paper 2025/440

AI for Code-based Cryptography

Mohamed Malhou

, Facebook (United States), Sorbonne University

Ludovic Perret, Graduate School of Computer Science and Advanced Technologies

Kristin Lauter, Facebook (United States)

Abstract

We introduce the use of machine learning in the cryptanalysis of code-based cryptography. Our focus is on distinguishing problems related to the security of NIST round-4 McEliece-like cryptosystems, particularly for Goppa codes used in ClassicMcEliece and Quasi-Cyclic Moderate Density Parity-Check (QC-MDPC) codes used in BIKE. We present DeepDistinguisher, a new algorithm for distinguishing structured codes from random linear codes that uses a transformer. The results show that the new distinguisher achieves a high level of accuracy in distinguishing Goppa codes, suggesting that their structure may be more recognizable by AI models. Our approach outperforms traditional attacks in distinguishing Goppa codes in certain settings and does generalize to larger code lengths without further training using a puncturing technique. We also present the first distinguishing results dedicated to MDPC and QC-MDPC codes.

Metadata

Available format(s): PDF
Category: Attacks and cryptanalysis
Publication info: Preprint.
Keywords: Classic McEliece Goppa Codes QC-MDPC Code Distinguishability Deep Learning Transformers
Contact author(s): mmalhou @ meta com
ludovic perret @ epita fr
klauter @ meta com
History: 2025-03-10: approved; 2025-03-07: received; See all versions
Short URL: https://ia.cr/2025/440
License: CC BY

BibTeX

@misc{cryptoeprint:2025/440,
      author = {Mohamed Malhou and Ludovic Perret and Kristin Lauter},
      title = {{AI} for Code-based Cryptography},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/440},
      year = {2025},
      url = {https://eprint.iacr.org/2025/440}
}