\(\textsf{ReSolveD} \) : Shorter Signatures from Regular Syndrome Decoding and VOLE-in-the-Head

We present \(\textsf{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 }\) – \(2{\times }\) improvement in terms of the common “signature size + public-key size” metric, while keeping the computational efficiency competitive.