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

Hongrui Cui; Hanlin Liu; Di Yan; Kang Yang; Yu Yu; Kaiyi Zhang

doi:10.1007/978-3-031-57718-5_8

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

Hongrui Cui, Hanlin Liu, Di Yan, Kang Yang, Yu Yu, Kaiyi Zhang

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

5 Scopus citations

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×–2× improvement in terms of the common “signature size + public-key size” metric, while keeping the computational efficiency competitive.

Original language	English
Title of host publication	Public-Key Cryptography – PKC 2024 - 27th IACR International Conference on Practice and Theory of Public-Key Cryptography, 2024, Proceedings
Editors	Qiang Tang, Vanessa Teague
Publisher	Springer Science and Business Media Deutschland GmbH
Pages	229-258
Number of pages	30
ISBN (Print)	9783031577208
DOIs	https://doi.org/10.1007/978-3-031-57718-5_8
State	Published - 2024
Externally published	Yes
Event	27th IACR International Conference on Practice and Theory of Public Key Cryptography, PKC 2024 - Sydney, Australia Duration: 15 Apr 2024 → 17 Apr 2024

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	14601 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	27th IACR International Conference on Practice and Theory of Public Key Cryptography, PKC 2024
Country/Territory	Australia
City	Sydney
Period	15/04/24 → 17/04/24

Access to Document

10.1007/978-3-031-57718-5_8

Cite this

Cui, H., Liu, H., Yan, D., Yang, K., Yu, Y., & Zhang, K. (2024). ReSolveD: Shorter Signatures from Regular Syndrome Decoding and VOLE-in-the-Head. In Q. Tang, & V. Teague (Eds.), Public-Key Cryptography – PKC 2024 - 27th IACR International Conference on Practice and Theory of Public-Key Cryptography, 2024, Proceedings (pp. 229-258). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 14601 LNCS). Springer Science and Business Media Deutschland GmbH. https://doi.org/10.1007/978-3-031-57718-5_8

Cui, Hongrui ; Liu, Hanlin ; Yan, Di et al. / ReSolveD : Shorter Signatures from Regular Syndrome Decoding and VOLE-in-the-Head. Public-Key Cryptography – PKC 2024 - 27th IACR International Conference on Practice and Theory of Public-Key Cryptography, 2024, Proceedings. editor / Qiang Tang ; Vanessa Teague. Springer Science and Business Media Deutschland GmbH, 2024. pp. 229-258 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{7da6ac9ebf4c4b46ac431c45ae7a7e1e,

title = "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×–2× improvement in terms of the common “signature size + public-key size” metric, while keeping the computational efficiency competitive.",

author = "Hongrui Cui and Hanlin Liu and Di Yan and Kang Yang and Yu Yu and Kaiyi Zhang",

note = "Publisher Copyright: {\textcopyright} International Association for Cryptologic Research 2024.; 27th IACR International Conference on Practice and Theory of Public Key Cryptography, PKC 2024 ; Conference date: 15-04-2024 Through 17-04-2024",

year = "2024",

doi = "10.1007/978-3-031-57718-5\_8",

language = "英语",

isbn = "9783031577208",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Science and Business Media Deutschland GmbH",

pages = "229--258",

editor = "Qiang Tang and Vanessa Teague",

booktitle = "Public-Key Cryptography – PKC 2024 - 27th IACR International Conference on Practice and Theory of Public-Key Cryptography, 2024, Proceedings",

address = "德国",

}

Cui, H, Liu, H, Yan, D, Yang, K, Yu, Y & Zhang, K 2024, ReSolveD: Shorter Signatures from Regular Syndrome Decoding and VOLE-in-the-Head. in Q Tang & V Teague (eds), Public-Key Cryptography – PKC 2024 - 27th IACR International Conference on Practice and Theory of Public-Key Cryptography, 2024, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 14601 LNCS, Springer Science and Business Media Deutschland GmbH, pp. 229-258, 27th IACR International Conference on Practice and Theory of Public Key Cryptography, PKC 2024, Sydney, Australia, 15/04/24. https://doi.org/10.1007/978-3-031-57718-5_8

ReSolveD: Shorter Signatures from Regular Syndrome Decoding and VOLE-in-the-Head. / Cui, Hongrui; Liu, Hanlin; Yan, Di et al.
Public-Key Cryptography – PKC 2024 - 27th IACR International Conference on Practice and Theory of Public-Key Cryptography, 2024, Proceedings. ed. / Qiang Tang; Vanessa Teague. Springer Science and Business Media Deutschland GmbH, 2024. p. 229-258 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 14601 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - ReSolveD

T2 - 27th IACR International Conference on Practice and Theory of Public Key Cryptography, PKC 2024

AU - Cui, Hongrui

AU - Liu, Hanlin

AU - Yan, Di

AU - Yang, Kang

AU - Yu, Yu

AU - Zhang, Kaiyi

PY - 2024

Y1 - 2024

N2 - 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×–2× improvement in terms of the common “signature size + public-key size” metric, while keeping the computational efficiency competitive.

AB - 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×–2× improvement in terms of the common “signature size + public-key size” metric, while keeping the computational efficiency competitive.

UR - https://www.scopus.com/pages/publications/85192208571

U2 - 10.1007/978-3-031-57718-5_8

DO - 10.1007/978-3-031-57718-5_8

M3 - 会议稿件

AN - SCOPUS:85192208571

SN - 9783031577208

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 229

EP - 258

BT - Public-Key Cryptography – PKC 2024 - 27th IACR International Conference on Practice and Theory of Public-Key Cryptography, 2024, Proceedings

A2 - Tang, Qiang

A2 - Teague, Vanessa

PB - Springer Science and Business Media Deutschland GmbH

Y2 - 15 April 2024 through 17 April 2024

ER -

Cui H, Liu H, Yan D, Yang K, Yu Y, Zhang K. ReSolveD: Shorter Signatures from Regular Syndrome Decoding and VOLE-in-the-Head. In Tang Q, Teague V, editors, Public-Key Cryptography – PKC 2024 - 27th IACR International Conference on Practice and Theory of Public-Key Cryptography, 2024, Proceedings. Springer Science and Business Media Deutschland GmbH. 2024. p. 229-258. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-031-57718-5_8