printlogo
http://www.ethz.ch/index_EN
First Annual Conference on Quantum Cryptography
 
Sitemap |
print
  

Merkle Puzzles in a Quantum World

poster-qcrypt-thumb

» download Poster or Flyer
» download Booklet

Sponsors

pauliohne

 

eth_logo_black

 

Logo_QSIT

 

Logo_nano-tera

 

CQT_Logo

 

Logo_IQC

 

Logo_IDQ

 

SNFlogo

 

dfg_logo_blau

Gilles Brassard, Peter Hoyer, Kassem Kalach, Marc Kaplan, Sophie Laplante and Louis Salvail

 

In 1974, Ralph Merkle proposed the first unclassified scheme for secure communications over insecure channels. When legitimate communicating parties are willing to spend an amount of computational effort proportional to some parameter N, an eavesdropper cannot break into their communication without spending a time proportional to N^2, which is quadratically more than the legitimate effort.

We showed in an earlier paper that Merkle's schemes are completely insecure against a quantum adversary, but that their security can be partially restored if the legitimate parties are also allowed to use quantum computation: the eavesdropper needed to spend a time proportional to N^{3/2} to break our earlier quantum scheme. Furthermore, all previous classical schemes could be broken completely by the onslaught of a quantum eavesdropper and we conjectured that this is unavoidable.

We give two novel key agreement schemes in the spirit of Merkle's. The first one can be broken by a quantum adversary that makes an effort proportional to N^{5/3} to implement a quantum random walk in a Johnson graph reminiscent of Andris Ambainis' quantum algorithm for the element distinctness problem. This attack is optimal up to logarithmic factors. Our second scheme is purely classical, yet it cannot be broken by a quantum eavesdropper who is only willing to expend effort proportional to that of the legitimate parties.

 

Wichtiger Hinweis:
Diese Website wird in älteren Versionen von Netscape ohne graphische Elemente dargestellt. Die Funktionalität der Website ist aber trotzdem gewährleistet. Wenn Sie diese Website regelmässig benutzen, empfehlen wir Ihnen, auf Ihrem Computer einen aktuellen Browser zu installieren. Weitere Informationen finden Sie auf
folgender Seite.

Important Note:
The content in this site is accessible to any browser or Internet device, however, some graphics will display correctly only in the newer versions of Netscape. To get the most out of our site we suggest you upgrade to a newer browser.
More information

© 2015 ETH Zurich | Imprint | Disclaimer | 5 August 2011
top