Projective Space Stern Decoding and Application to SDitH

Kévin Carrier (1) , Jean-Pierre Tillich (2) , Valerian Hatey (1)

1 ETIS - UMR 8051 - Equipes Traitement de l'Information et Systèmes
2 COSMIQ - Cryptologie symétrique, cryptologie fondée sur les codes et information quantique

We show that here standard decoding algorithms for generic linear codes over a finite field can speeded up by a factor which is essentially the size of the finite field by reducing it to a low weight codeword problem and working in the relevant projective space. We apply this technique to SDitH and show that the parameters of both the original submission and the updated version fall short of meeting the security requirements asked by the NIST.

Mots clés: Code-based Cryptography; Error correcting code; Post-quantum Cryptography; NIST; Syndrome decoding

Domaines: Informatique [cs]; Mathématiques [math]

Kévin Carrier, Jean-Pierre Tillich, Valerian Hatey. Projective Space Stern Decoding and Application to SDitH. Workshop on Advances in Asymmetric Cryptanalysis (AAC'24), Mar 2024, Abu Dabi, United Arab Emirates. ⟨hal-04519768⟩