CryptoDB
Kaiyi Zhang
NOTE: imports for ToSC and TCHES are no longer functioning.
Publications
Year
Venue
Title
2024
PKC
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.5X ~ 2X improvement in terms of the common “signature size + public-key size” metric, while keeping the computational efficiency competitive.
Coauthors
- Hongrui Cui (1)
- Hanlin Liu (1)
- Di Yan (1)
- Kang Yang (1)
- Yu Yu (1)
- Kaiyi Zhang (1)