Paper 2022/889
Quantum Rewinding for Many-Round Protocols
, Aalto UniversityAbstract
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
-
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}
}
