Paper 2023/1035

Short Signatures from Regular Syndrome Decoding in the Head

Eliana Carozza, Université Paris Cité
Geoffroy Couteau, CNRS, Université Paris Cité
Antoine Joux, CISPA Helmholtz Center for Information Security

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 $\mathbb{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 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).

Available format(s)
Cryptographic protocols
Publication info
A major revision of an IACR publication in EUROCRYPT 2023
post-quantum signaturecode-based signatureregular syndrome decodingzero-knowledge proof
Contact author(s)
carozza @ irif fr
couteau @ irif fr
joux @ cispa de
2023-07-05: approved
2023-07-03: received
See all versions
Short URL
Creative Commons Attribution


      author = {Eliana Carozza and Geoffroy Couteau and Antoine Joux},
      title = {Short Signatures from Regular Syndrome Decoding in the Head},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1035},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.