Paper 2022/889 Original: eprint.iacr.org/2022/889 ↗
Quantum Rewinding for Many-Round Protocols
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.
- History
- 2022-09-23: last updated
- 2022-07-07: published
- Short URL
- https://ia.cr/2022/889
- License
- https://creativecommons.org/licenses/by/4.0/
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}
}