Key Establishment a la Merkle in a Quantum World

摘要

In 1974, Ralph Merkle proposed the first unclassified protocol for secure communications over insecure channels. When legitimate communicating parties are willing to spend an amount of computational effort proportional to some parameterN, an eavesdropper cannot break into their communication without spending a time proportional toN2, which is quadratically more than the legitimate effort. Ina quantum world, however, Merkle's protocol is immediately broken by Grover's algorithm, but it is easily repaired if we are satisfied with a quantum protocol against which a quantum adversary needs to spend a time proportional to N3/2 in order to breakit. Can we do better? We give two new key establishment protocols in the spirit of Merkle's. The first one, which requires the legitimate parties to have access to a quantum computer, resists any quantum adversary who is not willing to make an effort at least proportional toN5/3, except with vanishing probability. Our second protocol is purely classical, yet it requires any quantum adversary to work asymptotically harder than the legitimate parties, again except with vanishing probability. Ineither case, security is proved for a typical run of the protocols: the probabilities are taken over the random (orquantum) choices made by the legitimate participants in order to establish their key as well as over the random (orquantum) choices made by the adversary who is trying to be privy toit.