cispa_all_3873.pdf (552.29 kB)

Syndrome Decoding in the Head: Shorter Signatures from Zero-Knowledge Proofs

Download (552.29 kB)
conference contribution
posted on 2023-11-29, 18:26 authored by Thibauld Feneuil, Antoine JouxAntoine Joux, Matthieu Rivain
Zero-knowledge proofs of knowledge are useful tools to de- sign signature schemes. The ongoing effort to build a quantum computer urges the cryptography community to develop new secure cryptographic protocols based on quantum-hard cryptographic problems. One of the few directions is code-based cryptography for which the strongest prob- lem is the syndrome decoding (SD) for random linear codes. This problem is known to be NP-hard and the cryptanalysis state of the art has been stable for many years. A zero-knowledge protocol for this problem was pioneered by Stern in 1993. Since its publication, many articles proposed optimizations, implementation, or variants. In this paper, we introduce a new zero-knowledge proof for the syndrome decoding problem on random linear codes. Instead of using permuta- tions like most of the existing protocols, we rely on the MPC-in-the- head paradigm in which we reduce the task of proving the low Hamming weight of the SD solution to proving some relations between specific polynomials. Specifically, we propose a 5-round zero-knowledge protocol that proves the knowledge of a vector x such that y = Hx and wt(x) ≤ w and which achieves a soundness error closed to 1/N for an arbitrary N. While turning this protocol into a signature scheme, we achieve a signa- ture size of 11-12 KB for 128-bit security when relying on the hardness of the SD problem on binary fields. Using larger fields (like F28 ), we can produce fast signatures of around 8 KB. This allows us to outperform Picnic3 and to be competitive with SPHINCS+, both post-quantum sig- nature candidates in the ongoing NIST standardization effort. Moreover, our scheme outperforms all the existing code-based signature schemes for the common “signature size + public key size” metric.


Preferred Citation

Thibauld Feneuil, Antoine Joux and Matthieu Rivain. Syndrome Decoding in the Head: Shorter Signatures from Zero-Knowledge Proofs. In: Advances in Cryptology (CRYPTO). 2022.

Primary Research Area

  • Algorithmic Foundations and Cryptography

Name of Conference

Advances in Cryptology (CRYPTO)

Legacy Posted Date


Open Access Type

  • Unknown


@inproceedings{cispa_all_3873, title = "Syndrome Decoding in the Head: Shorter Signatures from Zero-Knowledge Proofs", author = "Feneuil, Thibauld and Joux, Antoine and Rivain, Matthieu", booktitle="{Advances in Cryptology (CRYPTO)}", year="2022", }

Usage metrics


    No categories selected


    Ref. manager