Cryptology ePrint Archive: Report 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.

Category / Keywords: public-key cryptography / RQCS, digital signatures, cryptanalysis

Date: received 5 Feb 2019, last revised 17 Feb 2019

Contact author: keita xagawa zv at hco ntt co jp

Available format(s): PDF | BibTeX Citation

Note: Correct typo. Add references and a concurrent work by Lau and Tan at

Version: 20190218:053322 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]