تقرير
An efficient quantum parallel repetition theorem and applications
| العنوان: | An efficient quantum parallel repetition theorem and applications |
|---|---|
| المؤلفون: | Bostanci, John, Qian, Luowen, Spooner, Nicholas, Yuen, Henry |
| سنة النشر: | 2023 |
| المجموعة: | Computer Science Quantum Physics |
| مصطلحات موضوعية: | Quantum Physics, Computer Science - Computational Complexity, Computer Science - Cryptography and Security |
| الوصف: | 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. Comment: 58 pages, 9 fun algorithms to look at. To be published in STOC 2024 |
| نوع الوثيقة: | Working Paper |
| DOI: | 10.1145/3618260.3649603 |
| URL الوصول: | http://arxiv.org/abs/2311.10681 |
| رقم الأكسشن: | edsarx.2311.10681 |
| قاعدة البيانات: | arXiv |
| DOI: | 10.1145/3618260.3649603 |
|---|