Paper 2019/120

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

Keita Xagawa


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

Available format(s)
Public-key cryptography
Publication info
Preprint. MINOR revision.
RQCSdigital signaturescryptanalysis
Contact author(s)
keita xagawa zv @ hco ntt co jp
2019-02-18: last of 3 revisions
2019-02-13: received
See all versions
Short URL
Creative Commons Attribution


      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{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.