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

Abstract

Zero-knowledge proofs of knowledge are useful tools to design 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 problem 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 permutations 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 $\operatorname{wt}(x)\leq 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 signature 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 $\mathbb{F}_{2^8}$), we can produce fast signatures of around 8 KB. This allows us to outperform Picnic3 and to be competitive with SPHINCS+, both post-quantum signature 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.

Available format(s)
Category
Public-key cryptography
Publication info
A major revision of an IACR publication in CRYPTO 2022
DOI
10.1007/978-3-031-15979-4_19
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
See all versions
Short URL
https://ia.cr/2022/188

CC BY

BibTeX

@misc{cryptoeprint:2022/188,
author = {Thibauld Feneuil and Antoine Joux and Matthieu Rivain},
title = {Syndrome Decoding in the Head: Shorter Signatures from Zero-Knowledge Proofs},
howpublished = {Cryptology ePrint Archive, Paper 2022/188},
year = {2022},
doi = {10.1007/978-3-031-15979-4_19},
note = {\url{https://eprint.iacr.org/2022/188}},
url = {https://eprint.iacr.org/2022/188}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.