1 of 14

AI for Code-based Cryptography

Mohamed Malhou

​

PhD student @ Sorbonne Université & FAIR & EPITA

​

Co-supervised by Kristin Lauter, François Charton, Ludovic Perret

CBCrypto 2025

​

May 3rd

2 of 14

Cryptography in the post-quantum era

National Institute of Standards and Technology (NIST)

Category

Primary Algorithm

Alternate Algorithms

Public-Key Encryption/KEMs

CRYSTALS-Kyber

HQC

Digital Signatures

CRYSTALS-Dilithium

FALCON, SPHINCS+

Fourth Round KEM Finalists (2022-2025)

  • BIKE
  • Classic McEliece
  • HQC (selected as alternate in March 2025)
  • SIKE (withdrawn due to security concerns)

3 of 14

Classic McEliece

plaintext

​

​

Decode

​

​

ciphertext

Bob's Public Key

Bob's Private Key

Bob

Alice

4 of 14

Binary Irreducible Goppa Codes

  • A family of error-correcting codes defined over a finite field with q=2.
  • Parameterized by :
    • A set of distinct elements called the support.
    • A polynomial of degree t, irreducible.
  • Defined as the -kernel of

Where

  • Code dimension k >= n - mt
  • Corrects up to t errors in a codeword.

5 of 14

Security analysis of McEliece

​

  • Hardness of Decoding
  • Goppa Distinguishing Problem

Linear Codes

Goppa Codes

G

6 of 14

Some Distinguishers in the Literature

J.-C. Faugère, V. Gauthier-Umana, A. Otmani, L. Perret, J.-P. Tillich.

A Distinguisher for High Rate McEliece Cryptosystems.

IEEE-IT 2013

​

A. Couvreur, R. Mora, J.-P. Tillich.

A New Approach Based on Quadratic Forms to Attack the McEliece Cryptosystem.

Asiacrypt 2023.

​

H. Randriambololona.

The Syzygy Distinguisher.

EUROCRYPT 2025.

7 of 14

Approach: Classification task using a Transformer

g8

g1

g2

g3

g4

g5

g6

g7

Goppa

Random

8 of 14

Evaluation of the distinguishers in the literature

[Randriam 24 & CMT 23]

​

  1. Consider a field extension degree m (e.g. m= 6)
  2. For maximum n = q^m (e.g. n= 64), determine maximal distinguishable degree t.
  3. Fix t, determine minimal distinguishable n.

9 of 14

Results:

  • Model accuracy as a function of code length. The model is trained on Binary Goppa Codes with m=6 and t=3.
  • Scatter points indicate the evaluation accuracy of our model.
  • The scatter color indicates the range where the model was trained (n = 24 + 8k for k=0,1,..)

10 of 14

  • Heatmap of model accuracy for q=2, m=6 as a function of code length n and degree parameter t.

11 of 14

  • Heatmap of model accuracy for q=2, m=7 as a function of code length n and degree parameter t.

12 of 14

Can we do better than just distinguish ?

Training on a new task: Goppa Code Completion

1

1

1

0

1

0

1

0

0

1

0

1

0

0

0

0

1

1

1

0

1

0

0

0

1

0

1

0

1

0

1

0

1

0

1

1

1

0

0

0

0

1

1

1

1

0

0

0

0

1

0

1

0

1

0

0

0

0

1

0

1

1

0

0

1

0

1

0

1

1

1

0

1

0

1

0

0

1

0

1

0

0

0

0

0

1

1

1

0

1

0

0

0

1

0

1

0

0

1

0

1

0

1

0

1

1

1

0

0

0

0

0

1

1

1

1

0

0

0

0

1

0

1

0

1

0

0

0

0

1

0

1

1

0

0

1

0

1

0

1

13 of 14

Test Accuracy on n=64, m=6

​

14 of 14

Summary and Conclusion

Paper: Mohamed Malhou, Ludovic Perret, Kristin Lauter

AI for Code-based Cryptography

​

  • New class of attacks in code-based cryptography using AI
  • Improve SOTA Goppa distinguishers in toy examples.
    • What are the limits of this approach and how to estimate the complexity?
  • Results can be extended to (QC) MDPC Codes (BIKE).

Solution icons created by Canticons - Flaticon