Paper 2021/1576
Shared Permutation for Syndrome Decoding: New Zero-Knowledge Protocol and Code-Based Signature
Abstract
Zero-knowledge proofs are an important tool for many cryptographic protocols and applications. The threat of a coming quantum computer motivates the research for new zero-knowledge proof techniques for (or based on) post-quantum cryptographic problems. One of the few directions is code-based cryptography for which the strongest problem is the syndrome decoding (SD) of random linear codes. This problem is known to be NP-hard and the cryptanalysis state of affairs has been stable for many years. A zero-knowledge protocol for this problem was pioneered by Stern in 1993. As a simple public-coin three-round protocol, it can be converted to a post-quantum signature scheme through the famous Fiat-Shamir transform. The main drawback of this protocol is its high soundness error of
Metadata
- Available format(s)
-
PDF
- Category
- Public-key cryptography
- Publication info
- Published elsewhere. Designs, Codes and Cryptography
- DOI
- 10.1007/s10623-022-01116-1
- Keywords
- cryptographic protocols zero knowledge proofs syndrome decoding code-based signature
- Contact author(s)
-
thibauld feneuil @ cryptoexperts com
joux @ cispa de
matthieu rivain @ cryptoexperts com - History
- 2022-11-23: revised
- 2021-12-03: received
- See all versions
- Short URL
- https://ia.cr/2021/1576
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2021/1576, author = {Thibauld Feneuil and Antoine Joux and Matthieu Rivain}, title = {Shared Permutation for Syndrome Decoding: New Zero-Knowledge Protocol and Code-Based Signature}, howpublished = {Cryptology {ePrint} Archive, Paper 2021/1576}, year = {2021}, doi = {10.1007/s10623-022-01116-1}, url = {https://eprint.iacr.org/2021/1576} }