Merkle Puzzles are Optimal Export

@misc{citeulike:3129029, 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(n^2) queries to the oracle. This improves on the previous Omega(n^6) query attack given by Impagliazzo and Rudich (STOC '89). Our bound is optimal up to a constant factor since Merkle (CACM '78) gave an n query key exchange protocol in this model that cannot be broken by an adversary making o(n^2) queries.}, author = {Barak, Boaz and Mahmoody-Ghidary, Mohammad}, citeulike-article-id = {3129029}, citeulike-linkout-0 = {http://eprint.iacr.org/2008/032}, day = {23}, howpublished = {Cryptology ePrint Archive, Report 2008/032}, keywords = {cryptography, public-key, public-key-cryptography}, month = {Jan}, posted-at = {2008-08-16 22:05:16}, priority = {2}, title = {Merkle Puzzles are Optimal}, url = {http://eprint.iacr.org/2008/032}, year = {2008} }

TY - ELEC ID - citeulike:3129029 L3 - citeulike-article-id:3129029 N2 - 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(n^2) queries to the oracle. This improves on the previous Omega(n^6) query attack given by Impagliazzo and Rudich (STOC '89). Our bound is optimal up to a constant factor since Merkle (CACM '78) gave an n query key exchange protocol in this model that cannot be broken by an adversary making o(n^2) queries. TI - Merkle Puzzles are Optimal KW - cryptography KW - public-key KW - public-key-cryptography AU - Barak, Boaz AU - Mahmoody-Ghidary, Mohammad PY - 2008/Jan/23/ UR - http://eprint.iacr.org/2008/032 ER -