Welcome to the resource topic for 2023/385
Title:
Zero Knowledge Protocols and Signatures from the Restricted Syndrome Decoding Problem
Authors: Marco Baldi, Sebastian Bitzer, Alessio Pavoni, Paolo Santini, Antonia Wachter-Zeh, Violetta Weger
Abstract: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.
ePrint: https://eprint.iacr.org/2023/385
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .