Hamming Metric Code-Based Signature Scheme With Restricted Vectors
Chik How Tan, Theo Fanuela Prabowo · EPiC series in computing · 2025
We introduce HQCS-R, a novel Hamming-metric code-based signature scheme over Z_q. The security of the proposed scheme is based on the hardness of Hamming-metric restricted syndrome decoding problem for quasi cyclic codes, where the error vectors are restricted to a proper subset of Z_q^n. Assuming the hardness of this problem, we prove that HQCS-R is EUF-CMA secure in the classical random oracle model. Furthermore, we thoroughly analyze the security of the scheme, as well as compute a lower bound for the acceptance rate of signature generation. Based on these analyses, we present some concrete parameters for HQCS-R. In particular, for 128-bit security level, the public key and signature sizes of HQCS-R are 5888 bytes and 6265 bytes respectively.