Abstract
We prove that every key exchange protocol in the random oracle model in which the honest users make at most n queries to the oracle can be broken by an adversary making O(n2) queries to the oracle. This improves on the previous \(\Tilde{\Omega}(n^6)\) query attack given by Impagliazzo and Rudich (STOC ’89), and answers an open question posed by them. Our bound is optimal up to a constant factor since Merkle (CACM ’78) gave a key exchange protocol that can easily be implemented in this model with n queries and cannot be broken by an adversary making o(n2) queries.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Merkle, R.: Secure communications over insecure channels. Communications of the ACM 21(4), 294–299 (1978)
Cachin, M.: Unconditional security against memory-bounded adversaries. In: Kaliski Jr., B.S. (ed.) CRYPTO 1997. LNCS, vol. 1294, pp. 292–306. Springer, Heidelberg (1997)
Biham, E., Goren, Y.J., Ishai, Y.: Basing weak public-key cryptography on strong one-way functions. In: Canetti, R. (ed.) TCC 2008. LNCS, vol. 4948, pp. 55–72. Springer, Heidelberg (2008)
Canetti, R., Goldreich, O., Halevi, S.: The random oracle methodology, revisited. In: Proc. 30th STOC, pp. 209–218. ACM, New York (1998)
Diffie, W., Hellman, M.: New directions in cryptography. IEEE Transactions on Information Theory IT-22(6), 644–654 (1976)
Rivest, R.L., Shamir, A., Adleman, L.M.: A method for obtaining digital signatures and public-key cryptosystems. Communications of the ACM 21(2), 120–126 (1978)
Bellare, M., Rogaway, P.: Random oracles are practical: A paradigm for designing efficient protocols. In: Proceedings of the First Annual Conference on Computer and Communications Security, November 1993, pp. 62–73. ACM, New York (1993)
Impagliazzo, R., Rudich, S.: Limits on the provable consequences of one-way permutations. In: Proc. 21st STOC, pp. 44–61. ACM, New York (1989); Full version available from Russell Impagliazzo’s home page
Grover, L.K.: A fast quantum mechanical algorithm for database search. In: Annual Symposium on Theory of Computing, May 22–24, pp. 212–219 (1996)
Bennett, C.H., Brassard, G., Ekert, A.: Quantum cryptography. SCIAM: Scientific American 267 (1992)
Brassard, G., Salvail, L.: Quantum merkle puzzles. In: International Conference on Quantum, Nano and Micro Technologies (ICQNM), pp. 76–79. IEEE Computer Society, Los Alamitos (2008)
Barak, B., Mahmoody-Ghidary, M.: Merkle Puzzles are Optimal. Arxiv preprint arXiv:0801.3669v1 (2008); Preliminary version of this paper. Version 1 contained a bug that is fixed in this version
Sotakova, M.: Breaking one-round key-agreement protocols in the random oracle model. Cryptology ePrint Archive, Report 2008/053 (2008), http://eprint.iacr.org/
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Barak, B., Mahmoody-Ghidary, M. (2009). Merkle Puzzles Are Optimal — An O(n2)-Query Attack on Any Key Exchange from a Random Oracle. In: Halevi, S. (eds) Advances in Cryptology - CRYPTO 2009. CRYPTO 2009. Lecture Notes in Computer Science, vol 5677. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-03356-8_22
Download citation
DOI: https://doi.org/10.1007/978-3-642-03356-8_22
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-03355-1
Online ISBN: 978-3-642-03356-8
eBook Packages: Computer ScienceComputer Science (R0)