Paper 2024/040 Original: eprint.iacr.org/2024/040 ↗

ReSolveD: Shorter Signatures from Regular Syndrome Decoding and VOLE-in-the-Head

Abstract

We present ReSolveD, a new candidate post-quantum signature scheme under the regular syndrome decoding (RSD) assumption for random linear codes, which is a well-established variant of the well-known syndrome decoding (SD) assumption. Our signature scheme is obtained by designing a new zero-knowledge proof for proving knowledge of a solution to the RSD problem in the recent VOLE-in-the-head framework using a sketching scheme to verify that a vector has weight exactly one. We achieve a signature size of 3.99 KB with a signing time of 27.3 ms and a verification time of 23.1 ms on a single core of a standard desktop for a 128-bit security level. Compared to the state-of-the-art code-based signature schemes, our signature scheme achieves $1.5\times \sim 2\times$ improvement in terms of the common "signature size + public-key size" metric, while keeping the computational efficiency competitive.