TY - GEN
T1 - Zero Knowledge Protocols and Signatures from the Restricted Syndrome Decoding Problem
AU - Baldi, Marco
AU - Bitzer, Sebastian
AU - Pavoni, Alessio
AU - Santini, Paolo
AU - Wachter-Zeh, Antonia
AU - Weger, Violetta
N1 - Publisher Copyright:
© International Association for Cryptologic Research 2024.
PY - 2024
Y1 - 2024
N2 - The Restricted Syndrome Decoding Problem (R-SDP) cor- responds 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.
AB - The Restricted Syndrome Decoding Problem (R-SDP) cor- responds 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.
KW - Code-based Cryptography
KW - Post-Quantum Cryptography
KW - Restricted Errors
KW - Signature Scheme
KW - Syndrome Decoding Problem
UR - http://www.scopus.com/inward/record.url?scp=85191023936&partnerID=8YFLogxK
U2 - 10.1007/978-3-031-57722-2_8
DO - 10.1007/978-3-031-57722-2_8
M3 - Conference contribution
AN - SCOPUS:85191023936
SN - 9783031577215
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 243
EP - 274
BT - Public-Key Cryptography – PKC 2024 - 27th IACR International Conference on Practice and Theory of Public-Key Cryptography, 2024, Proceedings
A2 - Tang, Qiang
A2 - Teague, Vanessa
PB - Springer Science and Business Media Deutschland GmbH
T2 - 27th IACR International Conference on Practice and Theory of Public Key Cryptography, PKC 2024
Y2 - 15 April 2024 through 17 April 2024
ER -