Physics – Quantum Physics
Scientific paper
2011-08-11
Physics
Quantum Physics
24 pages, this is an extended version of the corresponding paper in the Proceedings of CRYPTO 2011
Scientific paper
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 establishment 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.
Brassard Gilles
Hoyer Peter
Kalach Kassem
Kaplan Marc
Laplante Sophie
No associations
LandOfFree
Merkle Puzzles in a Quantum World does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Merkle Puzzles in a Quantum World, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Merkle Puzzles in a Quantum World will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-275039