International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: On the Impossibility of Key Agreements from Quantum Random Oracles

Per Austrin , KTH Royal Institute of Technology in Stockholm
Hao Chung , Carnegie Mellon University
Kai-Min Chung , Academia Sinica
Shiuan Fu , Academia Sinica
Yao-Ting Lin , Academia Sinica
Mohammad Mahmoody , University of Virginia
Search ePrint
Search Google
Presentation: Slides
Conference: CRYPTO 2022
Abstract: We study the following question, first publicly posed by Hosoyamada and Yamakawa in 2018. Can parties A, B with local quantum computing power rely (only) on a random oracle and classical communication to agree on a key? (Note that A, B can now query the random oracle at quantum superpositions.) We make the first progress on the question above and prove the following. – When only one of the parties A is classical and the other party B is quantum powered, as long as they ask a total of d oracle queries and agree on a key with probability 1, then there is always a way to break the key agreement by asking O(d^2) number of classical oracle queries. – When both parties can make quantum queries to the random oracle, we introduce a natural conjecture, which if true would imply attacks with poly(d) classical queries to the random oracle. Our conjecture, roughly speaking, states that the multiplication of any two degree-d real-valued polynomials over the Boolean hypercube of influence at most δ = 1/ poly(d) is nonzero. We then prove our conjecture for exponentially small influences, which leads to an (unconditional) classical 2^O(md)-query attack on any such key agreement protocol, where m is the random oracle’s output length. – Since our attacks are classical, we then ask whether it is possible to find such classical attacks in general. We prove a barrier for this approach, by showing that if the folklore “simulation conjecture” about the possibility of simulating efficient-query quantum algorithms classically is false, then that implies a possible quantum protocol that cannot be broken by classical adversaries.
Video from CRYPTO 2022
  title={On the Impossibility of Key Agreements from Quantum Random Oracles},
  author={Per Austrin and Hao Chung and Kai-Min Chung and Shiuan Fu and Yao-Ting Lin and Mohammad Mahmoody},