International Association for Cryptologic Research

International Association
for Cryptologic Research


Short Signatures from Regular Syndrome Decoding in the Head

Eliana Carozza , IRIF, Université de Paris
Geoffroy Couteau , CNRS, IRIF, Université de Paris
Antoine Joux , CISPA, Helmholtz Center for Cybersecurity
DOI: 10.1007/978-3-031-30589-4_19 (login may be required)
Search ePrint
Search Google
Presentation: Slides
Conference: EUROCRYPT 2023
Abstract: 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 F_2 (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 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 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).
  title={Short Signatures from Regular Syndrome Decoding in the Head},
  author={Eliana Carozza and Geoffroy Couteau and Antoine Joux},