2011/08/11 by Gilles Brassard, Peter Hoyer, Brassard, Gilles +9 · 1 citation
Physics and Astronomy · #FOS: Physical sciences #Quantum Physics (quant-ph) #quant-ph
paper · pdf · doi:10.48550/arxiv.1108.2316
32 pages, this is a December 2014 much improved and extended version of our paper "Merkle puzzles in a quantum world" from the Proceedings of CRYPTO 2011, pp. 391-410
arxiv created 2015/02/13 · arxiv updated 2015/02/16
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 N2, 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 N3/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 N5/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 N3/2 in the same model.