International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Shiuan Fu

Publications and invited talks

Year
Venue
Title
2022
CRYPTO
On the Impossibility of Key Agreements from Quantum Random Oracles 📺
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.