Paper 2022/889

Quantum Rewinding for Many-Round Protocols

Russell W. F. Lai, Aalto University
Giulio Malavolta, Max Planck Institute for Security and Privacy
Nicholas Spooner, University of Warwick
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.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint.
Keywords
succinct arguments lattice Bulletproofs quantum knowledge-soundness
Contact author(s)
russell lai @ aalto fi
giulio malavolta @ hotmail it
nicholas spooner @ warwick ac uk
History
2022-09-23: revised
2022-07-07: received
See all versions
Short URL
https://ia.cr/2022/889
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2022/889,
      author = {Russell W. F. Lai and Giulio Malavolta and Nicholas Spooner},
      title = {Quantum Rewinding for Many-Round Protocols},
      howpublished = {Cryptology {ePrint} Archive, Paper 2022/889},
      year = {2022},
      url = {https://eprint.iacr.org/2022/889}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.