IACR News item: 24 March 2023
Marco Baldi, Sebastian Bitzer, Alessio Pavoni, Paolo Santini, Antonia Wachter-Zeh, Violetta Weger
ePrint Report
The Restricted Syndrome Decoding Problem (R-SDP) cor-
responds to the Syndrome Decoding Problem (SDP) with the additional
constraint that entries of the solution vector must live in a desired sub-
set of a finite field. In this paper we study how this problem can be
applied to the construction of signatures derived from Zero-Knowledge
(ZK) proofs. First, we show that R-SDP appears to be well suited for
this type of applications: almost all ZK protocols relying on SDP can be
modified to use R-SDP, with important reductions in the communication
cost. Then, we describe how R-SDP can be further specialized, so that
solutions can be represented with a number of bits that is slightly larger
than the security parameter (which clearly provides an ultimate lower
bound), thus enabling the design of ZK protocols with tighter and rather
competitive parameters. Finally, we show that existing ZK protocols can
greatly benefit from the use of R-SDP, achieving signature sizes in the
order of 7 kB, which are smaller than those of several other schemes ob-
tained from ZK protocols. For instance, this beats all schemes based on
the Permuted Kernel Problem (PKP), almost all schemes based on SDP
and several schemes based on rank metric problems.
Additional news items may be found on the IACR news page.