Key establishment \`a la Merkle in a quantum world

R. Merkle, “C.S. 244 Project Proposal”, 1974. Facsimile available at http://www.merkle.com/1974

1974

Earlier work this paper cites.

W. Diffie and M. E. Hellman, “New directions in cryptography”, IEEE Transactions on Information Theory

1976

Earlier work this paper cites.

R. Merkle, “Secure communications over insecure channels”, Communications of the ACM

1978

Earlier work this paper cites.

L. Carter and M. N. Wegman, “Universal classes of hash functions”, Journal of Computer and System Sciences

1979

Earlier work this paper cites.

C. H. Bennett, E. Bernstein, G. Brassard and U. V. Vazirani, “Strengths and weaknesses of quantum computing”, SIAM Journal on Computing

1997

Earlier work this paper cites.

G. Brassard, P. Høyer and A. Tapp, “Quantum algorithm for the collision problem”, http://arxiv.org/abs/quant-ph/9705002 , 1997

1997

Earlier work this paper cites.

L. K. Grover, “Quantum mechanics helps in searching for a needle in a haystack”, Physical Review Letters

1997

Earlier work this paper cites.

P. W. Shor, “Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer”, SIAM Journal on Computing

1997

Cited alongside, same era.

M. Boyer, G. Brassard, P. Høyer and A. Tapp, “Tight bounds on quantum searching”, Fortschritte der Physik

1998

Cited alongside, same era.

G. Brassard, P. Høyer, M. Mosca and A. Tapp, “Quantum amplitude amplification and estimation”, in Quantum Computation and Quantum Information , Samuel J. Lomonaco, Jr. (editor), AMS Contemporary Mathematics

2002

Cited alongside, same era.

A. Ambainis, “Quantum walk algorithm for element distinctness”, SIAM Journal on Computing,

2007

Cited alongside, same era.

P. Høyer, T. Lee and R. Špalek, “Negative weights make adversaries stronger”, Proceedings

2007

Cited alongside, same era.

B. Barak and M. Mahmoody–Ghidary, “Merkle puzzles are optimal — An O ⁡ ( n 2 ) O(n^{2}) –query

2009

Later among the works it cites.

A. Childs and R. Kothari, “Quantum query complexity of minor-closed graph properties”, Proceedings of 28th Symposium on Theoretical Aspects of Computer Science (STACS)

2011

Closest in time.

T. Lee, R. Mittal, B. W. Reichardt, R. Špalek and M. Szegedy, “Quantum query complexity of state conversion”, Proceedings of the IEEE 52nd Annual Symposium on Foundations of Computer Science (FOCS)

2011

Closest in time.

F. Magniez, A. Nayak, J. Roland and M.Santha, “Search via quantum walk”, SIAM Journal on Computing

2011

Closest in time.

D. Unruh, Objection raised during the question period when a preliminary version of this work was presented at the First Annual Conference on Quantum Cryptography, September 2011. Start at the 23rd minute of http://www.multimedia.ethz.ch/conferences/2011/qcrypt/ 2011-09-12/?doi=10.3930/ETHZ/AV-5b98752b-7584-4ad0-b7fc-29aaf06371f9