CryptoDB
Short Signatures from Regular Syndrome Decoding in the Head
| Authors: |
|
|---|---|
| Download: |
|
| 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). |
BibTeX
@inproceedings{eurocrypt-2023-32944,
title={Short Signatures from Regular Syndrome Decoding in the Head},
publisher={Springer-Verlag},
doi={10.1007/978-3-031-30589-4_19},
author={Eliana Carozza and Geoffroy Couteau and Antoine Joux},
year=2023
}