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, withdrawn 26 Feb 2019

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

Available format(s): (-- withdrawn --)

Version: 20190226:083950 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]