Paper 2022/1493
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.
Metadata
- Available format(s)
-
PDF
- 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
- 2022-10-31: received
- See all versions
- Short URL
- https://ia.cr/2022/1493
- License
-
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} }