### Enhanced pqsigRM: Code-Based Digital Signature Scheme with Short Signature and Fast Verification for Post-Quantum Cryptography

##### Abstract

We present a novel code-based digital signature scheme, called enhanced pqsigRM for post-quantum cryptography (PQC). This scheme is based on a modified Reed--Muller (RM) code, which reduces the signature size and verification time compared with existing code-based signature schemes. In fact, it strengthens pqsigRM submitted to NIST for post-quantum cryptography standardization. The proposed scheme has the advantage of the short signature size and fast verification and uses public codes that are more difficult to distinguish from random codes. We use $(U,U+V)$-codes with the high-dimensional hull to overcome the disadvantages of code-based schemes. The proposed decoder samples from coset elements with small Hamming weight for any given syndrome and efficiently finds such an element. Using a modified RM code, the proposed signature scheme resists various known attacks on RM-code-based cryptography. It has advantages on signature size, verification time, and proven security. For 128 bits of classical security, the signature size of the proposed signature scheme is 512 bytes, which corresponds to 1/4.7 of that of CRYSTALS-DILITHIUM, and the number of median verification cycles is 1,717,336, which corresponds to the five times of that of CRYSTALS-DILITHIUM.

Available format(s)
Category
Public-key cryptography
Publication info
Preprint.
Keywords
Code-based digital signatureserror correction codespost-quantum cryptography (PQC)Reed-Muller (RM) codes.
Contact author(s)
jgjo114 @ ccl snu ac kr
jsno @ snu ac kr
yongwoo @ inha ac kr
bravokoo @ gmail com
iamyskim @ chosun ac kr
History
2023-03-21: last of 3 revisions
See all versions
Short URL
https://ia.cr/2022/1493

CC0

BibTeX

@misc{cryptoeprint:2022/1493,
author = {Jinkyu Cho and Jong-Seon No and Yongwoo Lee and Zahyun Koo and Young-Sik Kim},
title = {Enhanced pqsigRM: Code-Based Digital Signature Scheme with Short Signature and Fast Verification for Post-Quantum Cryptography},
howpublished = {Cryptology ePrint Archive, Paper 2022/1493},
year = {2022},
note = {\url{https://eprint.iacr.org/2022/1493}},
url = {https://eprint.iacr.org/2022/1493}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.