Edinburgh Research Explorer

Provably secure key establishment against quantum adversaries

Research output: Chapter in Book/Report/Conference proceedingConference contribution

  • Alexandrs Belovs
  • Gilles Brassard
  • Peter Høyer
  • Marc Kaplan
  • Sophie Laplante
  • Louis Salvail

Related Edinburgh Organisations

Open Access permissions

Open

Documents

  • Download as Adobe PDF

    Accepted author manuscript, 702 KB, PDF document

    Licence: Creative Commons: Attribution (CC-BY)

http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8581
Original languageEnglish
Title of host publication12th Conference on Theory of Quantum Computation, Communication and Cryptography (TQC 17)
Place of PublicationParis, France
PublisherSchloss Dagstuhl - Leibniz-Zentrum für Informatik
Pages3:1--3:17
Number of pages17
Volume73
ISBN (Electronic)978-3-95977-034-7
DOIs
Publication statusPublished - 2018
Event 12th Conference on the Theory of Quantum Computation, Communication, and Cryptography - Université Pierre et Marie Curie, Paris, France
Duration: 14 Jun 201716 Jun 2017
http://tqc2017.lip6.fr/
http://tqc2017.lip6.fr/

Publication series

NameLeibniz International Proceedings in Informatics (LIPIcs)
Volume73
ISSN (Electronic)1868-8969

Conference

Conference 12th Conference on the Theory of Quantum Computation, Communication, and Cryptography
Abbreviated titleTQC 2017
CountryFrance
CityParis
Period14/06/1716/06/17
Internet address

Abstract

At Crypto 2011, some of us had proposed a family of cryptographic protocols for key establishment capable of protecting quantum and classical legitimate parties unconditionally against a quantum eavesdropper in the query complexity model. Unfortunately, our security proofs were unsatisfactory from a cryptographically meaningful perspective because they were sound only in a worst-case scenario. Here, we extend our results and prove that for any e > 0, there is a classical protocol that allows the legitimate parties to establish a common key after O(N) expected queries to a random oracle, yet any quantum eavesdropper will have a vanishing probability of learning their key after O(N^{1.5-e}) queries to the same oracle. The vanishing probability applies to a typical run of the protocol. If we allow the legitimate parties to use a quantum computer as well, their advantage over the quantum eavesdropper becomes arbitrarily close to the quadratic advantage that classical legitimate parties enjoyed over classical eavesdroppers in the seminal 1974 work of Ralph Merkle. Along the way, we develop new tools to give lower bounds on the number of quantum queries required to distinguish two probability distributions. This method in itself could have multiple applications in cryptography. We use it here to study average-case quantum query complexity, for which we develop a new composition theorem of independent interest.

Download statistics

No data available

ID: 40919008