  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. Two of us showed in 2008 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 now two novel key establishment schemes in the spirit of Merkle's.
The first one can be broken by a quantum adversary who makes an effort
proportional to N^{5/3}, which is the optimal attack against this scheme. Our
second scheme is purely classical, yet it cannot be broken by a quantum
eavesdropper who is only willing to expend an effort proportional to that of
the legitimate parties.
  We then introduce two families of more elaborate protocols. The first family
consists in quantum protocols whose security is arbitrarily close to quadratic
in the query complexity model. The second is a family of classical protocols
whose security against a quantum adversary is arbitrarily close to N^{3/2} in
the same model.
