Cryptanalysis of a rank-based signature with short public keys

Nicolas Aragon (1) , Olivier Blazy (2) , Jean-Christophe Deneuville (3) , Philippe Gaborit (1) , Terry Shue Chien Lau (4) , Chik How Tan (4) , Keita Xagawa (5)

1 XLIM-MATHIS - Mathématiques & Sécurité de l'information
2 XLIM-DMI - DMI
3 ENAC - Ecole Nationale de l'Aviation Civile
4 NUS - National University of Singapore
5 NTT Corporation

Following Schnorr framework for obtaining digital signatures, Song et al. recently proposed a new instantiation of a signature scheme featuring small public keys from coding assumptions in rank metric, which was accepted at PKC'19. Their proposal makes use of rank quasi-cyclic (RQC) codes to reduce the public key size. We show that it is possible to turn a valid, legitimate signature into an efficiently solvable decoding problem, which allows to recover the randomness used for signing and hence the secret key, from a single signature, in about the same amount of time as required for signing

Mots clés: Post-quantum cryptography; Coding theory; Rank metric; RQC; Signature; Cryptanalysis

Domaines: Informatique [cs]; Cryptographie et sécurité [cs.CR]

Nicolas Aragon, Olivier Blazy, Jean-Christophe Deneuville, Philippe Gaborit, Terry Shue Chien Lau, et al.. Cryptanalysis of a rank-based signature with short public keys. Designs, Codes and Cryptography, 2020, 88 (4), pp.643-653. ⟨10.1007/s10623-019-00702-0⟩. ⟨hal-02613891⟩