2023-1035.pdf (1006.61 kB)

Short Signatures from Regular Syndrome Decoding in the Head

Download (1006.61 kB)
conference contribution
posted on 2024-03-25, 13:15 authored by Eliana Carozza, Geoffroy Couteau, Antoine Joux


We introduce a new candidate post-quantum digital signature scheme from the regular syndrome decoding (RSD) assumption, an established variant of the syndrome decoding assumption which asserts that it is hard to find w-regular solutions to systems of linear equations over F2 (a vector is regular if it is a concatenation of w unit vectors). Our signature is obtained by introducing and compiling a new 5-round zero-knowledge proof system constructed using the MPC-in-the-head paradigm. At the heart of our result is an efficient MPC protocol in the preprocessing model that checks the correctness of a regular syndrome decoding instance by using a share ring-conversion mechanism.  The analysis of our construction is non-trivial and forms a core technical contribution of our work. It requires careful combinatorial analysis and combines several new ideas, such as analyzing soundness in a relaxed setting where a cheating prover is allowed to use any witness sufficiently close to a regular vector. We complement our analysis with an in-depth overview of existing attacks against RSD.  Our signatures are competitive with the best-known code-based signatures, ranging from 12.52 KB (fast setting, with a signing time of the order of a few milliseconds on a single core of a standard laptop) to about 9 KB (short setting, with estimated signing time of the order of 15ms).


Primary Research Area

  • Algorithmic Foundations and Cryptography

Name of Conference

International Conference on the Theory and Application of Cryptographic Techniques (EuroCrypt)



Page Range



Springer Nature

Open Access Type

  • Not Open Access


@inproceedings{Carozza:Couteau:Joux:2023, title = "Short Signatures from Regular Syndrome Decoding in the Head", author = "Carozza, Eliana" AND "Couteau, Geoffroy" AND "Joux, Antoine", year = 2023, month = 4, pages = "532--563", publisher = "Springer Nature", issn = "1611-3349", doi = "10.1007/978-3-031-30589-4_19" }