Cryptanalysis of a rank-based signature with short public keys

Nicolas Aragon; Olivier Blazy; Jean-Christophe Deneuville; Philippe Gaborit; Terry Shue Chien Lau; Chik How Tan; Keita Xagawa

doi:10.1007/s10623-019-00702-0

Journal articles

Cryptanalysis of a rank-based signature with short public keys

Nicolas Aragon ¹ Olivier Blazy ² Jean-Christophe Deneuville ³ Philippe Gaborit ¹ Terry Shue Chien Lau ⁴ Chik How Tan ⁴ Keita Xagawa ⁵

1 XLIM-MATHIS - Mathématiques & Sécurité de l'information

XLIM - XLIM : MATHIS

2 XLIM-DMI - DMI

XLIM - XLIM

3 ENAC - Ecole Nationale de l'Aviation Civile

4 NUS - National University of Singapore

5 NTT Corporation

Abstract : 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

Keywords : Cryptanalysis Post-quantum cryptography Coding theory Rank metric RQC Signature

Document type :

Journal articles

Domain :

Computer Science [cs] / Cryptography and Security [cs.CR]

Complete list of metadata

Cited literature [28 references] Display Hide Download

https://hal-enac.archives-ouvertes.fr/hal-02613891
Contributor : Laurence Porte <>
Submitted on : Wednesday, May 20, 2020 - 3:47:10 PM
Last modification on : Thursday, March 11, 2021 - 3:37:39 PM

Cryptanalysis of a rank-based signature with short public keys

File

Identifiers

Collections

Citation

Export

Metrics

86

213

Cryptanalysis of a rank-based signature with short public keys

File

Identifiers

Collections

Citation

Export

Share

Metrics

86

213