More Web Proxy on the site http://driver.im/

research-article

Open access

An Efficient Quantum Parallel Repetition Theorem and Applications

Authors:

Nicholas Spooner,

Henry YuenAuthors Info & Claims

STOC 2024: Proceedings of the 56th Annual ACM Symposium on Theory of Computing

Pages 1478 - 1487

https://doi.org/10.1145/3618260.3649603

Published: 11 June 2024 Publication History

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. 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. As immediate applications, we show how to derive hardness amplification theorems for quantum bit commitment schemes (answering a question of Yan), EFI pairs (answering a question of Brakerski, Canetti, and Qian), public-key quantum money schemes (answering a question of Aaronson and Christiano), and quantum zero-knowledge argument systems. We also derive an XOR lemma for quantum predicates as a corollary.

References

[1]

Scott Aaronson and Paul Christiano. 2013. Quantum Money from Hidden Subspaces. Theory of Computing, 9, 9 (2013), 349–401. https://doi.org/10.4086/toc.2013.v009a009

[2]

Andris Ambainis, Robert Špalek, and Ronald de Wolf. 2006. A New Quantum Lower Bound Method,: With Applications to Direct Product Theorems and Time-Space Tradeoffs. In Proceedings of the Thirty-Eighth Annual ACM Symposium on Theory of Computing (STOC ’06). Association for Computing Machinery, New York, NY, USA. 618–633. isbn:1595931341 https://doi.org/10.1145/1132516.1132604

Digital Library

[3]

Mihir Bellare, Russell Impagliazzo, and Moni Naor. 1997. Does parallel repetition lower the error in computationally sound protocols? In Proceedings 38th Annual Symposium on Foundations of Computer Science. IEEE Computer Society, USA. 374–383. https://doi.org/10.1109/SFCS.1997.646126

[4]

Itay Berman, Iftach Haitner, and Eliad Tsfadia. 2020. A Tight Parallel Repetition Theorem for Partially Simulatable Interactive Arguments via Smooth KL-Divergence. In Advances in Cryptology – CRYPTO 2020, Daniele Micciancio and Thomas Ristenpart (Eds.). Springer International Publishing, Cham. 544–573. isbn:978-3-030-56877-1 https://doi.org/10.1007/978-3-030-56877-1_19

Digital Library

[5]

Nir Bitansky, Zvika Brakerski, and Yael Tauman Kalai. 2022. Constructive Post-Quantum Reductions. In Advances in Cryptology – CRYPTO 2022, Yevgeniy Dodis and Thomas Shrimpton (Eds.). Springer Nature Switzerland, Cham. 654–683. isbn:978-3-031-15982-4 https://doi.org/10.1007/978-3-031-15982-4_22

Digital Library

[6]

Nir Bitansky and Huijia Lin. 2018. One-Message Zero Knowledge and Non-malleable Commitments. In Theory of Cryptography, Amos Beimel and Stefan Dziembowski (Eds.). Springer International Publishing, Cham. 209–234. isbn:978-3-030-03807-6 https://doi.org/10.1007/978-3-030-03807-6_8

Digital Library

[7]

John Bostanci, Yuval Efron, Tony Metger, Alexander Poremba, Luowen Qian, and Henry Yuen. 2023. Unitary Complexity and the Uhlmann Transformation Problem. arxiv:2306.13073.

[8]

Zvika Brakerski. 2023. Black-Hole Radiation Decoding Is Quantum Cryptography. In Advances in Cryptology – CRYPTO 2023, Helena Handschuh and Anna Lysyanskaya (Eds.). Springer Nature Switzerland, Cham. 37–65. isbn:978-3-031-38554-4 https://doi.org/10.1007/978-3-031-38554-4_2

Digital Library

[9]

Zvika Brakerski, Ran Canetti, and Luowen Qian. 2023. On the Computational Hardness Needed for Quantum Cryptography. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023), Yael Tauman Kalai (Ed.) (Leibniz International Proceedings in Informatics (LIPIcs), Vol. 251). Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl, Germany. 21 pages. isbn:978-3-95977-263-1 issn:1868-8969 https://doi.org/10.4230/LIPIcs.ITCS.2023.24

[10]

Ran Canetti, Shai Halevi, and Michael Steiner. 2005. Hardness Amplification of Weakly Verifiable Puzzles. In Proceedings of the Second International Conference on Theory of Cryptography (TCC’05). Springer-Verlag, Berlin, Heidelberg. 17–33. isbn:3540245731 https://doi.org/10.1007/978-3-540-30576-7_2

Digital Library

[11]

Nai-Hui Chia, Kai-Min Chung, and Takashi Yamakawa. 2021. A Black-Box Approach to Post-Quantum Zero-Knowledge in Constant Rounds. In Advances in Cryptology – CRYPTO 2021, Tal Malkin and Chris Peikert (Eds.). Springer International Publishing, Cham. 315–345. isbn:978-3-030-84242-0 https://doi.org/10.1007/978-3-030-84242-0_12

Digital Library

[12]

Alessandro Chiesa, Fermi Ma, Nicholas Spooner, and Mark Zhandry. 2022. Post-Quantum Succinct Arguments: Breaking the Quantum Rewinding Barrier. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS). IEEE Computer Society, Los Alamitos, CA, USA. 49–58. https://doi.org/10.1109/FOCS52979.2021.00014

[13]

Kai-Min Chung and Feng-Hao Liu. 2010. Parallel Repetition Theorems for Interactive Arguments. In Theory of Cryptography, Daniele Micciancio (Ed.). Springer Berlin Heidelberg, Berlin, Heidelberg. 19–36. isbn:978-3-642-11799-2 https://doi.org/10.1007/978-3-642-11799-2_2

Digital Library

[14]

Kai-Min Chung and Rafael Pass. 2015. Tight Parallel Repetition Theorems for Public-Coin Arguments Using KL-Divergence. In Theory of Cryptography, Yevgeniy Dodis and Jesper Buus Nielsen (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg. 229–246. isbn:978-3-662-46497-7 https://doi.org/10.1007/978-3-662-46497-7_9

[15]

Léo Colisson. 2019. Equivalents of Yao’s Xor lemma to rounds, or other hardness amplification methods? https://crypto.stackexchange.com/questions/66983/equivalents-of-yaos-xor-lemma-to-rounds-or-other-hardness-amplification-method Accessed: 2023-09-15

[16]

Yevgeniy Dodis, Abhishek Jain, Tal Moran, and Daniel Wichs. 2012. Counterexamples to Hardness Amplification beyond Negligible. In Theory of Cryptography, Ronald Cramer (Ed.). Springer Berlin Heidelberg, Berlin, Heidelberg. 476–493. isbn:978-3-642-28914-9 https://doi.org/10.1007/978-3-642-28914-9_27

Digital Library

[17]

Rachit Garg, Dakshita Khurana, George Lu, and Brent Waters. 2021. Black-Box Non-interactive Non-malleable Commitments. In Advances in Cryptology – EUROCRYPT 2021, Anne Canteaut and François-Xavier Standaert (Eds.). Springer International Publishing, Cham. 159–185. isbn:978-3-030-77883-5 https://doi.org/10.1007/978-3-030-77883-5_6

Digital Library

[18]

András Gilyén, Yuan Su, Guang Hao Low, and Nathan Wiebe. 2019. Quantum Singular Value Transformation and beyond: Exponential Improvements for Quantum Matrix Arithmetics. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (STOC 2019). Association for Computing Machinery, New York, NY, USA. 193–204. isbn:9781450367059 https://doi.org/10.1145/3313276.3316366

Digital Library

[19]

Oded Goldreich, Noam Nisan, and Avi Wigderson. 2011. On Yao’s XOR-Lemma. Springer Berlin Heidelberg, Berlin, Heidelberg. 273–301. isbn:978-3-642-22670-0 https://doi.org/10.1007/978-3-642-22670-0_23

[20]

Sam Gunn, Nathan Ju, Fermi Ma, and Mark Zhandry. 2023. Commitments to Quantum States. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing (STOC 2023). Association for Computing Machinery, New York, NY, USA. 1579–1588. isbn:9781450399135 https://doi.org/10.1145/3564246.3585198

Digital Library

[21]

Iftach Haitner. 2009. A Parallel Repetition Theorem for Any Interactive Argument. In IEEE 50th Annual Symposium on Foundations of Computer Science (FOCS 2009). IEEE Computer Society, Los Alamitos, CA, USA. issn:0272-5428 https://doi.org/10.1109/FOCS.2009.50

[22]

Johan Håstad, Rafael Pass, Douglas Wikström, and Krzysztof Pietrzak. 2010. An Efficient Parallel Repetition Theorem. In Theory of Cryptography, Daniele Micciancio (Ed.). Springer Berlin Heidelberg, Berlin, Heidelberg. 1–18. isbn:978-3-642-11799-2 https://doi.org/10.1007/978-3-642-11799-2_1

Digital Library

[23]

Minki Hhan, Tomoyuki Morimae, and Takashi Yamakawa. 2023. From the Hardness of Detecting Superpositions to Cryptography: Quantum Public Key Encryption and Commitments. In Advances in Cryptology – EUROCRYPT 2023, Carmit Hazay and Martijn Stam (Eds.). Springer Nature Switzerland, Cham. 639–667. isbn:978-3-031-30545-0 https://doi.org/10.1007/978-3-031-30545-0_22

Digital Library

[24]

Julia Kempe, Hirotada Kobayashi, Keiji Matsumoto, and Thomas Vidick. 2007. Using Entanglement in Quantum Multi-Prover Interactive Proofs. computational complexity, 18 (2007), 12, https://doi.org/10.1007/s00037-009-0275-3

[25]

Dakshita Khurana and Amit Sahai. 2017. How to Achieve Non-Malleability in One or Two Rounds. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS). IEEE Computer Society, Los Alamitos, CA, USA. 564–575. issn:0272-5428 https://doi.org/10.1109/FOCS.2017.58

[26]

Alexei Kitaev and John Watrous. 2000. Parallelization, Amplification, and Exponential Time Simulation of Quantum Interactive Proof Systems. In Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing (STOC ’00). Association for Computing Machinery, New York, NY, USA. 608–617. isbn:1581131844 https://doi.org/10.1145/335305.335387

Digital Library

[27]

Troy Lee and Jérémie Roland. 2013. A strong direct product theorem for quantum query complexity. computational complexity, 22, 2 (2013), 01 Jun, 429–462. issn:1420-8954 https://doi.org/10.1007/s00037-013-0066-8

[28]

Leonid A. Levin. 1987. One way functions and pseudorandom generators. Combinatorica, 7, 4 (1987), 01 Dec, 357–363. issn:1439-6912 https://doi.org/10.1007/BF02579323

Digital Library

[29]

Xiao Liang, Omkant Pandey, and Takashi Yamakawa. 2023. A New Approach to Post-Quantum Non-Malleability. In 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS). IEEE Computer Society, Los Alamitos, CA, USA. 568–579. https://doi.org/10.1109/FOCS57990.2023.00041

[30]

Alex Lombardi, Fermi Ma, and Nicholas Spooner. 2022. Post-Quantum Zero Knowledge, Revisited or: How to Do Quantum Rewinding Undetectably. In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS). IEEE Computer Society, Los Alamitos, CA, USA. 851–859. https://doi.org/10.1109/FOCS54457.2022.00086

[31]

Chris Marriott and John Watrous. 2005. Quantum Arthur–Merlin games. computational complexity, 14, 2 (2005), 01 Jun, 122–152. issn:1420-8954 https://doi.org/10.1007/s00037-005-0194-x

Digital Library

[32]

Tomoyuki Morimae and Takashi Yamakawa. 2022. One-Wayness in Quantum Cryptography. arxiv:2210.03394.

[33]

Rafael Pass and Muthuramakrishnan Venkitasubramaniam. 2012. A Parallel Repetition Theorem for Constant-Round Arthur-Merlin Proofs. ACM Transactions on Computation Theory (TOCT), 4, 4 (2012), Article 10, nov, 22 pages. issn:1942-3454 https://doi.org/10.1145/2382559.2382561

Digital Library

[34]

Krzysztof Pietrzak and Douglas Wikström. 2012. Parallel Repetition of Computationally Sound Protocols Revisited. Journal of Cryptology, 25, 1 (2012), 01 Jan, 116–135. issn:1432-1378 https://doi.org/10.1007/s00145-010-9090-x

Digital Library

[35]

Roy Radian and Or Sattath. 2019. Semi-Quantum Money. In Proceedings of the 1st ACM Conference on Advances in Financial Technologies (AFT ’19). Association for Computing Machinery, New York, NY, USA. 132–146. isbn:9781450367325 https://doi.org/10.1145/3318041.3355462

Digital Library

[36]

Ronen Shaltiel and Emanuele Viola. 2008. Hardness Amplification Proofs Require Majority. In Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing (STOC ’08). Association for Computing Machinery, New York, NY, USA. 589–598. isbn:9781605580470 https://doi.org/10.1145/1374376.1374461

Digital Library

[37]

Alexander A. Sherstov. 2011. Strong Direct Product Theorems for Quantum Communication and Query Complexity. In Proceedings of the Forty-Third Annual ACM Symposium on Theory of Computing (STOC ’11). Association for Computing Machinery, New York, NY, USA. 41–50. isbn:9781450306911 https://doi.org/10.1145/1993636.1993643

Digital Library

[38]

John Watrous. 2009. Zero-Knowledge against Quantum Attacks. SIAM J. Comput., 39, 1 (2009), 25–58. https://doi.org/10.1137/060670997

Digital Library

[39]

Jun Yan. 2022. General Properties of Quantum Bit Commitments (Extended Abstract). In Advances in Cryptology – ASIACRYPT 2022, Shweta Agrawal and Dongdai Lin (Eds.). Springer Nature Switzerland, Cham. 628–657. isbn:978-3-031-22972-5 https://doi.org/10.1007/978-3-031-22972-5_22

Digital Library

[40]

Andrew C. Yao. 1982. Theory and application of trapdoor functions. In 2013 IEEE 54th Annual Symposium on Foundations of Computer Science. IEEE Computer Society, Los Alamitos, CA, USA. 80–91. issn:0272-5428 https://doi.org/10.1109/SFCS.1982.95

Cited By

Malavolta GMorimae TWalter MYamakawa T(2024)Exponential Quantum One-Wayness and EFI PairsSecurity and Cryptography for Networks10.1007/978-3-031-71070-4_6(121-138)Online publication date: 11-Sep-2024
https://dl.acm.org/doi/10.1007/978-3-031-71070-4_6
Chung KGoldin EGray M(2024)On Central Primitives for Quantum Cryptography with Classical CommunicationAdvances in Cryptology – CRYPTO 202410.1007/978-3-031-68394-7_8(215-248)Online publication date: 18-Aug-2024
https://doi.org/10.1007/978-3-031-68394-7_8

Index Terms

An Efficient Quantum Parallel Repetition Theorem and Applications
1. Theory of computation
  1. Computational complexity and cryptography

Recommendations

Secure Two-Party Computation in a Quantum World
Applied Cryptography and Network Security
Abstract
Secure multi-party computation has been extensively studied in the past years and has reached a level that is considered practical for several applications. The techniques developed thus far have been steadily optimized for performance and were ...
Somewhere Statistical Soundness, Post-Quantum Security, and SNARGs
Theory of Cryptography
Abstract
The main conceptual contribution of this paper is a unification of two leading paradigms for constructing succinct argument systems, namely Kilian’s protocol and the $BMW$ (Biehl-Meyer-Wetzel) heuristic. We define the notion of a multi-extractable ...
Layering Quantum-Resistance into Classical Digital Signature Algorithms
Information Security
Abstract
It is proven that asymmetric key cryptographic systems that rely on Integer Factorization or Discrete Logarithm as the underlying hard problem are vulnerable to quantum computers. Using Shor’s algorithm on a large-enough quantum computer, an ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

STOC 2024: Proceedings of the 56th Annual ACM Symposium on Theory of Computing

June 2024

2049 pages

ISBN:9798400703836

DOI:10.1145/3618260

General Chairs:
Bojan Mohar
Simon Fraser University, Canada
,
Igor Shinkar
Simon Fraser University, Canada
,
Program Chair:
Ryan O'Donnell
Carnegie Mellon University, USA

Copyright © 2024 Owner/Author.

This work is licensed under a Creative Commons Attribution International 4.0 License.

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 11 June 2024

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

DARPA
AFOSR
NSF CAREER

Conference

STOC '24

Sponsor:

SIGACT

STOC '24: 56th Annual ACM Symposium on Theory of Computing

June 24 - 28, 2024

BC, Vancouver, Canada

Acceptance Rates

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Upcoming Conference

STOC '25

Sponsor:
sigact

57th Annual ACM Symposium on Theory of Computing (STOC 2025)

June 23 - 27, 2025

Prague , Czech Republic

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
196
Total Downloads

Downloads (Last 12 months)196
Downloads (Last 6 weeks)72

Reflects downloads up to 10 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Malavolta GMorimae TWalter MYamakawa T(2024)Exponential Quantum One-Wayness and EFI PairsSecurity and Cryptography for Networks10.1007/978-3-031-71070-4_6(121-138)Online publication date: 11-Sep-2024
https://dl.acm.org/doi/10.1007/978-3-031-71070-4_6
Chung KGoldin EGray M(2024)On Central Primitives for Quantum Cryptography with Classical CommunicationAdvances in Cryptology – CRYPTO 202410.1007/978-3-031-68394-7_8(215-248)Online publication date: 18-Aug-2024
https://doi.org/10.1007/978-3-031-68394-7_8

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents