A New Path to Code-based Signatures via Identification Schemes with Restricted Errors
This work addresses the need for more efficient code-based cryptographic schemes, offering incremental improvements for secure digital signatures.
The authors tackled the problem of constructing efficient code-based digital signatures by introducing a variant of the Syndrome Decoding Problem (R-SDP) and proving its NP-completeness, leading to compact public keys and significantly reduced communication costs in Zero-Knowledge Identification schemes.
In this paper we introduce a variant of the Syndrome Decoding Problem (SDP), that we call Restricted SDP (R-SDP), in which the entries of the searched vector are defined over a subset of the underlying finite field. We prove the NP-completeness of R-SDP, via a reduction from the classical SDP, and describe algorithms which solve such new problem. We study the properties of random codes under this new decoding perspective, in the fashion of traditional coding theory results, and assess the complexity of solving a random R-SDP instance. As a concrete application, we describe how Zero-Knowledge Identification (ZK-ID) schemes based on SDP can be tweaked to rely on R-SDP, and show that this leads to compact public keys as well as significantly reduced communication costs. Thus, these schemes offer an improved basis for the construction of code-based digital signature schemes derived from identification schemes through the well-know Fiat-Shamir transformation.