Cryptology ePrint Archive: Report 2019/678

A Modified pqsigRM: RM Code-Based Signature Scheme

Yongwoo Lee and Wijik Lee and Young-Sik Kim and Jong-Seon No

Abstract: We propose a novel signature scheme based on a modified Reed--Muller (RM) code, which reduces the signing complexity and key size compared to existing code-based signature schemes. This cheme is called as the modified pqsigRM, and corresponds to an improvement of pqsigRM, the proposal submitted to NIST. Courtois, Finiasz, and Sendrier (CFS) proposed a code-based signature scheme using the Goppa codes based on a full domain hash approach. However, owing to the properties of Goppa codes, the CFS signature scheme has drawbacks such as signing complexity and large key size. We overcome these disadvantages of the CFS signature scheme using partially permuted RM code and its decoding, which finds a near codeword for any received vector. Using a partially permuted RM code, the signature scheme resists various known attacks on the RM code-based cryptography. Additionally, we further modify the RM codes by row insertion/deletion of the generator matrix and thereafter resolve the problems reported in the post-quantum cryptography forum by NIST, such as the Hamming weight distribution of the public code.

Category / Keywords: public-key cryptography / Code-based cryptography, Courtois, Finiasz, and Sendrier (CFS) signature scheme, digital signatures, post-quantum cryptography (PQC), Reed-Muller (RM) code

Date: received 6 Jun 2019

Contact author: yongwool at ccl snu ac kr,iamyskim@chosun ac kr,jsno@snu ac kr

Available format(s): PDF | BibTeX Citation

Note: This manuscript is submitted on IEEE Transactions on Information Forensics and Security.

Version: 20190611:082105 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]