Paper 2023/385
Zero Knowledge Protocols and Signatures from the Restricted Syndrome Decoding Problem
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
Metadata
- Available format(s)
-
PDF
- Category
- Public-key cryptography
- Publication info
- A minor revision of an IACR publication in PKC 2024
- Keywords
- Code-based CryptographySignature SchemePost-quantum CryptographyRestricted ErrorsSyndrome 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}, url = {https://eprint.iacr.org/2023/385} }