Paper 2019/678

A Modified pqsigRM: RM Code-Based Signature Scheme

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


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.

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

Available format(s)
Public-key cryptography
Publication info
Preprint. MINOR revision.
Code-based cryptographyCourtoisFiniaszand Sendrier (CFS) signature schemedigital signaturespost-quantum cryptography (PQC)Reed-Muller (RM) code
Contact author(s)
yongwool @ ccl snu ac kr
iamyskim @ chosun ac kr
jsno @ snu ac kr
2019-06-11: received
Short URL
Creative Commons Attribution


      author = {Yongwoo Lee and Wijik Lee and Young-Sik Kim and Jong-Seon No},
      title = {A Modified pqsigRM: RM Code-Based Signature Scheme},
      howpublished = {Cryptology ePrint Archive, Paper 2019/678},
      year = {2019},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.