COMPUTER SCIENCE/DISCRETE MATH I | |

Topic: | Merkle Puzzles are Optimal |

Speaker: | Mohammad Mohmoody Ghidary |

Affiliation: | Princeton University |

Date: | Monday, April 7 |

Time/Room: | 11:15am - 12:15pm/S-101 |

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 $\Tilde{O}(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. Our result extends to an $O(n^2)$ query attack in the random permutation model improving on the pervious $\Tilde{O}(n^{12})$ attack of Impagliazzo and Rudich. This bound again optimal up to a constant factor since Merkle's protocol can be adapted to this model as well. Joint work with Boaz Barak