Paper 2019/678

A Modified pqsigRM: RM Code-Based Signature Scheme

Yongwoo Lee, Wijik Lee, 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.

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

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
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
History
2019-06-11: received
Short URL
https://ia.cr/2019/678
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2019/678,
      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},
      url = {https://eprint.iacr.org/2019/678}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.