## Merkle Puzzles in a Quantum World

** Gilles Brassard** (1),
**Peter Høyer** (2),
**Kassem Kalach** (1),
**Marc Kaplan** (1),
**Sophie Laplante** (3), and
**Louis Salvail** (1)

(1) *
Département d'informatique et de recherche opérationnelle,
Université de Montréal, Succursale Centre-ville
Montréal (QC), Canada*

(2) * Department of Computer Science, University of Calgary,
Calgary, AB, Canada*, and

(3) *LRI, Université Paris-Sud, Orsay, France*
**Abstract.**
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.

**Keywords:**
Merkle Puzzles, Public Key Distribution, Quantum Cryptography.