TY - JOUR
T1 - Cryptanalysis of a rank-based signature with short public keys
AU - Aragon, Nicolas
AU - Blazy, Olivier
AU - Deneuville, Jean Christophe
AU - Gaborit, Philippe
AU - Lau, Terry Shue Chien
AU - Tan, Chik How
AU - Xagawa, Keita
N1 - Publisher Copyright:
© 2019, Springer Science+Business Media, LLC, part of Springer Nature.
PY - 2020/4/1
Y1 - 2020/4/1
N2 - 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.
AB - 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.
KW - Coding theory
KW - Cryptanalysis
KW - Post-quantum cryptography
KW - RQC
KW - Rank metric
KW - Signature
U2 - 10.1007/s10623-019-00702-0
DO - 10.1007/s10623-019-00702-0
M3 - Article
AN - SCOPUS:85076604501
SN - 0925-1022
VL - 88
SP - 643
EP - 653
JO - Designs, Codes, and Cryptography
JF - Designs, Codes, and Cryptography
IS - 4
ER -