New Construction of Code-Based Signature Schemes
摘要
In this paper, we present a novel approach to construct code-based digital signature schemes. Our focus is on addressing the efficiency issues stemming from the low proportion of decodable syndromes in classical CFS signature scheme. To overcome this challenge, we introduce a well-defined syndrome subspace wherein all syndromes can be efficiently decoded. Additionally, our scheme differs from traditional code-based approaches by employing a novel method for constructing public and private keys, replacing permutation matrices with invertible matrices. This transformation yields a public key matrix that is statistically indistinguishable from a random matrix. We demonstrate that our scheme achieves existential unforgeability under an adaptive chosen message attack (EUF-CMA) in the random oracle model. Comparative analysis against other code-based signature schemes, such as Wave and Enhanced pqsigRM, reveals significant advantages in both public key and signature sizes. Furthermore, compared to the three post-quantum signature schemes (Crystals-Dilithium, Falcon, and Sphincs \(+\) ) selected as finalists by NIST PQC, our scheme still maintains a significant advantage in terms of signature size.