Paper 2019/120

Cryptanalysis of a New Code-based Signature Scheme with Shorter Public Key in PKC 2019

Keita Xagawa

Abstract

Song, Huang, Mu, and Wu proposed a new code-based signature scheme, the Rank Quasi-Cyclic Signature (RQCS) scheme (PKC 2019, Cryptology ePrint Archive 2019/053), which is based on an IND-CCA2 KEM scheme, RQC, proposed by Aguilar Melchor et al. (NIST PQC Standardization Round 1). Their scheme is an analogue to the Schnorr signature scheme. In this short note, we investigate the security of the RQCS scheme. We report a key-recovery known-message attack by following the discussion in Aragon, Blazy, Gaborit, Hauteville, and Zémor (Cryptology ePrint Archive 2018/1192) and an experimental result. The key-recovery attack requires only one signature to retrieve a secret key and recovers a secret key within 10 seconds.

Note: Correct typo. Add references and a concurrent work by Lau and Tan at https://arxiv.org/abs/1902.00241

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
RQCSdigital signaturescryptanalysis
Contact author(s)
keita xagawa zv @ hco ntt co jp
History
2019-02-18: last of 3 revisions
2019-02-13: received
See all versions
Short URL
https://ia.cr/2019/120
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2019/120,
      author = {Keita Xagawa},
      title = {Cryptanalysis of a New Code-based Signature Scheme with Shorter Public Key in PKC 2019},
      howpublished = {Cryptology ePrint Archive, Paper 2019/120},
      year = {2019},
      note = {\url{https://eprint.iacr.org/2019/120}},
      url = {https://eprint.iacr.org/2019/120}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.