Zero Knowledge Protocols and Signatures from the Restricted Syndrome Decoding Problem

Marco Baldi; Sebastian Bitzer; Alessio Pavoni; Paolo Santini; Antonia Wachter-Zeh; Violetta Weger

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

Abstract

The Restricted Syndrome Decoding Problem (R-SDP) corresponds to the Syndrome Decoding Problem (SDP) with the additional constraint that all entries of the solution error vector must live in a fixed subset of the finite field. In this paper, we study how this problem can be applied to the construction of signatures derived from Zero-Knowledge (ZK) protocols. First, we show that R-SDP appears to be well-suited for this type of application: ZK protocols relying on SDP can easily be modified to use R-SDP, resulting in significant reductions in the communication cost. We then introduce and analyze a variant of R-SDP, which we call R-SDP$(G)$, with the property that solution vectors can be represented with a number of bits that is slightly larger than the security parameter (which clearly provides an ultimate lower bound). This enables the design of competitive ZK protocols. 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 submitted to NIST's additional call for post-quantum digital signatures.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: A minor revision of an IACR publication in PKC 2024
Keywords: Code-based Cryptography Signature Scheme Post-quantum Cryptography Restricted Errors Syndrome Decoding Problem
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
History: 2024-01-22: revised; 2023-03-17: received; See all versions
Short URL: https://ia.cr/2023/385
License: CC BY

BibTeX

@misc{cryptoeprint:2023/385,
      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{https://eprint.iacr.org/2023/385}},
      url = {https://eprint.iacr.org/2023/385}
}