Merkle Puzzles in a Quantum World

Tweet Arxiv - 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.

24 page research paper

While Ralph Merkle was delivering the 2005 International Association for Cryptologic Research (IACR) Distinguished Lecture at the Crypto annual conference in Santa Barbara, describing his original unpublished 1974 scheme [16] for public key establishment (much simpler and more elegant than his subsequently published, yet better known, Merkle Puzzles [17]), one of us (Brassard) immediately realized that this scheme was totally insecure against an eavesdropper equipped with a quantum computer. The obvious question was: can Merkle’s idea be repaired and made secure again in our quantum world? The defining characteristics of Merkle’s protocol are that (1) the legitimate parties communicate strictly through an authenticated classical channel on which eavesdropping is unrestricted and (2) a protocol is deemed to be secure if the cryptanalytic effort required of the eavesdropper to learn the key established by the legitimate parties grows super-linearly with the legitimate work.

We partially repaired Merkle’s scheme in Ref. [8] with a scheme in which the eavesdropper needed an amount of work in (N3/2) to obtain the key established by quantum legitimate parties whose amount of work is in O(N). This was not quite as good as the work in (N2) required by a classical eavesdropper against Merkle’s original scheme, but significantly better than the work in O(N) sufficient for a quantum eavesdropper against the same scheme

[8] G. Brassard and L. Salvail, “Quantum Merkle puzzles”, Proceedings of Second International Conference on Quantum, Nano, and Micro Technologies (ICQNM08), Sainte Luce, Martinique, February 2008, pp. 76–79.

If you liked this article, please give it a quick review on ycombinator or StumbleUpon. Thanks