Cryptology ePrint Archive: Report 2019/053

A New Code-based Signature Scheme with Shorter Public Key

Yongcheng Song and Xinyi Huang and Yi Mu and Wei Wu

Abstract: Code-based signature has been believed to be a useful authentication tool for post-quantum cryptography. There have been some attempts to construct efficient code-based signatures; however, existing code-based signature schemes suffer from large public-key size, which has affected their applicability. It has been a challenging research task to construct efficient code-based signatures with a shorter public-key size. In this paper, we propose an efficient code-based signature scheme, which offers a short public key size. Our scheme is an analogue to the Schnorr signature where we utilize random rank double circulant codes and matrix-vector product used in the Rank Quasi-Cyclic (RQC) scheme introduced by Melchor et al. (NIST 2017).We provide the security proof of our signature scheme by reducing it to the Rank Quasi-Cyclic Syndrome Decoding (RQCSD) problem. Our work provides an example for the construction of code-based signatures for the applications which require short public keys.

Category / Keywords: cryptographic protocols / Post-Quantum Cryptography, Rank Metric Codes, Digital Signatures

Original Publication (with minor differences): IACR-PKC-2019

Date: received 18 Jan 2019, last revised 18 Jan 2019

Contact author: yongchengsong at outlook com,xyhuang81@gmail com,ymu ieee@gmail com,ispec2014@qq com

Available format(s): PDF | BibTeX Citation

Version: 20190125:204017 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]