Intrusion-resilient key exchange in the bounded retrieval model

David Cash, Yan Zong Ding, Yevgeniy Dodis, Wenke Lee, Richard Lipton, Shabsi Walfish

Research output: Chapter in Book/Report/Conference proceedingConference contribution


We construct an intrusion-resilient symmetric-key authenticated key exchange (AKE) protocol in the bounded retrieval model. The model employs a long shared private key to cope with an active adversary who can repeatedly compromise the user's machine and perform any efficient computation on the entire shared key. However, we assume that the attacker is communication bounded and unable to retrieve too much information during each successive break-in. In contrast, the users read only a small portion of the shared key, making the model quite realistic in situations where storage is much cheaper than bandwidth. The problem was first studied by Dziembowski [Dzi06a], who constructed a secure AKE protocol using random oracles. We present a general paradigm for constructing intrusion-resilient AKE protocols in this model, and show how to instantiate it without random oracles. The main ingredients of our construction are UC-secure password authenticated key exchange and tools from the bounded storage model.

Original languageEnglish (US)
Title of host publicationTheory of Cryptography - 4th Theory of Cryptography Conference, TCC 2007, Proceedings
PublisherSpringer Verlag
Number of pages20
ISBN (Print)9783540709350
StatePublished - 2007
Event4th Theory of Cryptography Conference, TCC 2OO7 - Amsterdam, Netherlands
Duration: Feb 21 2007Feb 24 2007

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume4392 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other4th Theory of Cryptography Conference, TCC 2OO7

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Intrusion-resilient key exchange in the bounded retrieval model'. Together they form a unique fingerprint.

Cite this