Marc Kaplan, Université de Montréal
Abstract
In 1974, Ralph Merkle proposed the first secure protocol for classical key distribution over a public channel. When legitimate participants are willing to spend an amount of computational effort proportional to some parameter N, an eavesdropper cannot break their communication without an effort of at least N^2. Unfortunately, Merkle's scheme is completely insecure if the eavesdropper has access to quantum resources. In a previous attempt, Brassard and Salvail partially restored the security if the legitimate participant are also allowed to use quantum resources. In their scheme, the eavesdropper needs a time of order of N^3/2 to break the protocol.
We introduce to new protocols improving the result of Brassard and Salvail. In the first one, the players use quantum resources and the eavesdropper needs a time proportional to N^5/3 to break the protocol. We give an attack based on quantum walks on Johnson graphs, and prove a matching lower bound. The second protocol is purely classical, yet an adversary needs to spend more resources than the legitimate players to break the protocol, even if it has access to quantum resources. The best possible quantum eavesdropping strategy against this classical scheme needs a time in the order of N^13/12. This opens the door to restoring the security of Merkle's seminal approach against quantum attackers even if the legitimate parties do not have any quantum computing capabilities.