kth.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
On the Impossibility of Key Agreements from Quantum Random Oracles
KTH, School of Electrical Engineering and Computer Science (EECS), Computer Science, Theoretical Computer Science, TCS.ORCID iD: 0000-0001-8217-0158
Carnegie Mellon Univ, Pittsburgh, PA USA..
Acad Sinica, Taipei, Taiwan..
Acad Sinica, Taipei, Taiwan..
Show 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

Available from: 2022-12-12 Created: 2022-12-12 Last updated: 2022-12-12Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full textScopus

Authority records

Austrin, Per

Search in DiVA

By author/editor
Austrin, Per
By organisation
Theoretical Computer Science, TCS
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 57 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf