Paper 2023/1783
An efficient quantum parallel repetition theorem and applications
, Columbia University, Boston University, University of Warwick, New York University, Columbia UniversityAbstract
We prove a tight parallel repetition theorem for $3$-message computationally-secure quantum interactive protocols between an efficient challenger and an efficient adversary. We also prove under plausible assumptions that the security of $4$-message computationally secure protocols does not generally decrease under parallel repetition. These mirror the classical results of Bellare, Impagliazzo, and Naor [BIN97]. Finally, we prove that all quantum argument systems can be generically compiled to an equivalent $3$-message argument system, mirroring the transformation for quantum proof systems [KW00, KKMV07]. As immediate applications, we show how to derive hardness amplification theorems for quantum bit commitment schemes (answering a question of Yan [Yan22]), EFI pairs (answering a question of Brakerski, Canetti, and Qian [BCQ23]), public-key quantum money schemes (answering a question of Aaronson and Christiano [AC13]), and quantum zero-knowledge argument systems. We also derive an XOR lemma [Yao82] for quantum predicates as a corollary.
Metadata
- Available format(s)
-
PDF
- Category
- Foundations
- Publication info
- Preprint.
- Keywords
- post-quantumaverage-case complexitydirect productpuzzle
- Contact author(s)
-
chb2154 @ columbia edu
luowenq @ bu edu
nickspoon0 @ gmail com
hyuen @ cs columbia edu - History
- 2023-11-20: approved
- 2023-11-17: received
- See all versions
- Short URL
- https://ia.cr/2023/1783
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2023/1783,
author = {John Bostanci and Luowen Qian and Nicholas Spooner and Henry Yuen},
title = {An efficient quantum parallel repetition theorem and applications},
howpublished = {Cryptology ePrint Archive, Paper 2023/1783},
year = {2023},
note = {\url{https://eprint.iacr.org/2023/1783}},
url = {https://eprint.iacr.org/2023/1783}
}
