s10623-022-01116-1.pdf (707.43 kB)

Shared permutation for syndrome decoding: new zero-knowledge protocol and code-based signature

Download (707.43 kB)
journal contribution
posted on 2024-03-25, 08:00 authored by Thibauld Feneuil, Antoine Joux, Matthieu Rivain

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 \(\mathcal {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 a 128-bit security. This represents a significant improvement over previous constructions based on the syndrome decoding problem for random linear codes.


Primary Research Area

  • Algorithmic Foundations and Cryptography


Designs, Codes and Cryptography



Page Range



Springer Nature

Open Access Type

  • Not Open Access

Sub Type

  • Article


@article{Feneuil:Joux:Rivain:2023, title = "Shared permutation for syndrome decoding: new zero-knowledge protocol and code-based signature", author = "Feneuil, Thibauld" AND "Joux, Antoine" AND "Rivain, Matthieu", year = 2023, month = 2, journal = "Designs, Codes and Cryptography", number = "2", pages = "563--608", publisher = "Springer Nature", issn = "0925-1022", doi = "10.1007/s10623-022-01116-1" }