An efficient quantum parallel repetition theorem and applications

John Bostanci; Luowen Qian; Nicholas Spooner; Henry Yuen

Paper 2023/1783

An efficient quantum parallel repetition theorem and applications

John Bostanci

, Columbia University

Luowen Qian

, Boston University

Nicholas Spooner

, University of Warwick, New York University

Henry Yuen

, Columbia University

Abstract

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.

Note: Full version.

Metadata

Available format(s): PDF
Category: Foundations
Publication info: Published elsewhere. Major revision. STOC 2024
DOI: 10.1145/3618260.3649603
Keywords: post-quantum average-case complexity direct product puzzle
Contact author(s): chb2154 @ columbia edu
luowenq @ bu edu
nickspoon0 @ gmail com
hyuen @ cs columbia edu
History: 2024-04-16: revised; 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},
      doi = {10.1145/3618260.3649603},
      note = {\url{https://eprint.iacr.org/2023/1783}},
      url = {https://eprint.iacr.org/2023/1783}
}