Quantum Rewinding for Many-Round Protocols

Russell W. F. Lai, Giulio Malavolta, Nicholas Spooner

Research output: Chapter in Book/Report/Conference proceedingConference article in proceedingsScientificpeer-review

3 Citations (Scopus)

Abstract

We investigate the security of succinct arguments against quantum adversaries. Our main result is a proof of knowledge-soundness in the post-quantum setting for a class of multi-round interactive protocols, including those based on the recursive folding technique of Bulletproofs. To prove this result, we devise a new quantum rewinding strategy, the first that allows for rewinding across many rounds. This technique applies to any protocol satisfying natural multi-round generalizations of special soundness and collapsing. For our main result, we show that recent Bulletproofs-like protocols based on lattices satisfy these properties, and are hence sound against quantum adversaries.
Original languageEnglish
Title of host publicationTheory of Cryptography
Subtitle of host publication20th International Conference, TCC 2022, Chicago, IL, USA, November 7–10, 2022, Proceedings, Part I
EditorsEike Kiltz, Vinod Vaikuntanathan
PublisherSpringer
Pages 80–109
ISBN (Electronic)978-3-031-22318-1
ISBN (Print)978-3-031-22317-4
DOIs
Publication statusPublished - 2023
MoE publication typeA4 Conference publication
EventTheory of Cryptography Conference - Chicago, United States
Duration: 7 Nov 202210 Nov 2022
Conference number: 20

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume13747
ISSN (Print)0302-9743

Conference

ConferenceTheory of Cryptography Conference
Abbreviated titleTCC
Country/TerritoryUnited States
CityChicago
Period07/11/202210/11/2022

Fingerprint

Dive into the research topics of 'Quantum Rewinding for Many-Round Protocols'. Together they form a unique fingerprint.

Cite this