Paper 2022/218

On the Impossibility of Key Agreements from Quantum Random Oracles

Per Austrin, Hao Chung, Kai-Min Chung, Shiuan Fu, Yao-Ting Lin, and Mohammad Mahmoody

Abstract

We study the following question, first publicly posed by Hosoyamada and Yamakawa in 2018. Can parties Alice and Bob with quantum computing power and classical communication rely only on a random oracle (that can be queried in quantum superposition) to agree on a key that is private from eavesdroppers? We make the first progress on the question above and prove the following. When only one of the parties is classical and the other party 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 oracle's output length. Since our attacks are classical, we then ask whether it is always possible to find classical attacks on key agreements with imperfect completeness in the quantum random oracle model. We proves a barrier for this approach, by showing that if the folklore “Simulation Conjecture” (first formally stated by Aaronson and Ambainis in 2009) about the possibility of simulating efficient-query quantum algorithms using efficient-query classical algorithms is false, then there is in fact such a secure key agreement in the quantum random oracle model that cannot be broken classically.