Paper 2024/040
ReSolveD: Shorter Signatures from Regular Syndrome Decoding and VOLE-in-the-Head
, Shanghai Jiao Tong University, Shanghai Qi Zhi Institute, State Key Laboratory of Cryptology, State Key Laboratory of Cryptology, Shanghai Jiao Tong University, Shanghai Qi Zhi Institute, Shanghai Jiao Tong UniversityAbstract
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.
Metadata
- Available format(s)
-
PDF
- Category
- Public-key cryptography
- Publication info
- Published elsewhere. PKC 2024
- Contact author(s)
-
rickfreeman @ sjtu edu cn
hans1024 @ sjtu edu cn
yand @ sklc org
yangk @ sklc org
yuyu @ yuyu hk
kzoacn @ sjtu edu cn - History
- 2024-01-10: approved
- 2024-01-10: received
- See all versions
- Short URL
- https://ia.cr/2024/040
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2024/040,
author = {Hongrui Cui and Hanlin Liu and Di Yan and Kang Yang and Yu Yu and Kaiyi Zhang},
title = {{ReSolveD}: Shorter Signatures from Regular Syndrome Decoding and {VOLE}-in-the-Head},
howpublished = {Cryptology {ePrint} Archive, Paper 2024/040},
year = {2024},
url = {https://eprint.iacr.org/2024/040}
}
