International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Quantum Rewinding for Many-Round Protocols

Authors:
Russell W. F. Lai , Friedrich-Alexander-Universität Erlangen-Nürnberg
Giulio Malavolta , Max Planck Institute for Security and Privacy
Nicholas Spooner , University of Warwick
Download:
Search ePrint
Search Google
Presentation: Slides
Conference: TCC 2022
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.
BibTeX
@inproceedings{tcc-2022-32627,
  title={Quantum Rewinding for Many-Round Protocols},
  publisher={Springer-Verlag},
  author={Russell W. F. Lai and Giulio Malavolta and Nicholas Spooner},
  year=2022
}