On the Impossibility of Key Agreements from Quantum Random OraclesShow others and affiliations
2022 (English)In: Advances In Cryptology - CRYPTO 2022, PT II / [ed] Dodis, Y Shrimpton, T, Springer Nature , 2022, Vol. 13508, p. 165-194Conference paper, Published paper (Refereed)
Abstract [en]
We study the following question, first publicly posed by Hosoyamada and Yamakawa in 2018. Can parties A, B 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 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 delta = 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 prove 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.
Place, publisher, year, edition, pages
Springer Nature , 2022. Vol. 13508, p. 165-194
Series
Lecture Notes in Computer Science, ISSN 0302-9743 ; 13508
National Category
Computer Sciences
Identifiers
URN: urn:nbn:se:kth:diva-322323DOI: 10.1007/978-3-031-15979-4_6ISI: 000886792700006Scopus ID: 2-s2.0-85141677504OAI: oai:DiVA.org:kth-322323DiVA, id: diva2:1718092
Conference
42nd Annual International Cryptology Conference (CRYPTO), AUG 15-18, 2022, Univ Calif, Santa Barbara, CA
Note
QC 20221212
Part of proceedings: ISBN 978-3-031-15978-7; 978-3-031-15979-4
2022-12-122022-12-122022-12-12Bibliographically approved