Paper 2023/385

Zero Knowledge Protocols and Signatures from the Restricted Syndrome Decoding Problem

Marco Baldi, Marche Polytechnic University
Sebastian Bitzer, Technical University of Munich
Alessio Pavoni, Marche Polytechnic University
Paolo Santini, Marche Polytechnic University
Antonia Wachter-Zeh, Technical University of Munich
Violetta Weger, Technical University of Munich

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.

Available format(s)
Public-key cryptography
Publication info
Code-based CryptographySignature Scheme
Contact author(s)
m baldi @ staff univpm it
sebastian bitzer @ tum de
s1101018 @ studenti univpm it
p santini @ staff univpm it
antonia wachter-zeh @ tum de
violetta weger @ tum de
2023-03-24: approved
2023-03-17: received
See all versions
Short URL
Creative Commons Attribution


      author = {Marco Baldi and Sebastian Bitzer and Alessio Pavoni and Paolo Santini and Antonia Wachter-Zeh and Violetta Weger},
      title = {Zero Knowledge Protocols and Signatures from the Restricted Syndrome Decoding Problem},
      howpublished = {Cryptology ePrint Archive, Paper 2023/385},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.