Paper 2021/1576

Shared Permutation for Syndrome Decoding: New Zero-Knowledge Protocol and Code-Based Signature

Thibauld Feneuil, CryptoExperts (France), Sorbonne University
Antoine Joux, Helmholtz Center for Information Security
Matthieu Rivain, CryptoExperts (France)

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 $2/3$, meaning that it should be repeated $\approx 1.7\lambda$ times to reach a $\lambda$-bit security. In this paper, we improve this three-decade-old state of affairs by introducing a new zero-knowledge proof for the syndrome decoding problem on random linear codes. Our protocol achieves a soundness error of 1/n for an arbitrary n in complexity O(n). Our construction requires the verifier to trust some of the variables sent by the prover which can be ensured through a cut-and-choose approach. We provide an optimized version of our zero-knowledge protocol which achieves arbitrary soundness through parallel repetitions and merged cut-and-choose phase. While turning this protocol into a signature scheme, we achieve a signature size of 17 KB for 128-bit security. This represents a significant improvement over previous constructions based on the syndrome decoding problem for random linear codes.

Available format(s)
Public-key cryptography
Publication info
Published elsewhere. Designs, Codes and Cryptography
cryptographic protocols zero knowledge proofs syndrome decoding code-based signature
Contact author(s)
thibauld feneuil @ cryptoexperts com
joux @ cispa de
matthieu rivain @ cryptoexperts com
2022-11-23: revised
2021-12-03: received
See all versions
Short URL
Creative Commons Attribution


      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},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.