  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.
