International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

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

Authors:
Hongrui Cui , Shanghai Jiao Tong University
Hanlin Liu , Shanghai Qi Zhi Institute
Di Yan , State Key Laboratory of Cryptology
Kang Yang , State Key Laboratory of Cryptology
Yu Yu , Shanghai Jiao Tong University
Kaiyi Zhang , Shanghai Jiao Tong University
Download:
Search ePrint
Search Google
Presentation: Slides
Conference: PKC 2024
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.
BibTeX
@inproceedings{pkc-2024-33706,
  title={ReSolveD: Shorter Signatures from Regular Syndrome Decoding and VOLE-in-the-Head},
  publisher={Springer-Verlag},
  author={Hongrui Cui and Hanlin Liu and Di Yan and Kang Yang and Yu Yu and Kaiyi Zhang},
  year=2024
}