International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: Key Regression: Enabling Efficient Key Distribution for Secure Distributed Storage

Kevin Fu
Seny Kamara
Tadayoshi Kohno
Search ePrint
Search Google
Abstract: The Plutus file system introduced the notion of key rotation as a means to derive a sequence of temporally-related keys from the most recent key. In this paper we show that, despite natural intuition to the contrary, key rotation schemes cannot generically be used to key other cryptographic objects; in fact, keying an encryption scheme with the output of a key rotation scheme can yield a composite system that is insecure. To address these shortcomings, we introduce a new cryptographic object called a key regression scheme, and we propose three constructions that are provably secure under standard cryptographic assumptions. We implement key regression in a secure file system and empirically show that key regression can significantly reduce the bandwidth requirements of a content publisher under realistic workloads using lazy revocation. Our experiments also serve as the first empirical evaluation of either a key rotation or key regression scheme.
  title={Key Regression: Enabling Efficient Key Distribution for Secure Distributed Storage},
  booktitle={IACR Eprint archive},
  keywords={Key regression, key rotation, lazy revocation, key distribution, content distribution network, hash chain, security proofs.},
  note={An extended abstract of this paper appears in ISOC Network and Distributed System Security Symposium (NDSS), February 2006. This is the full version. 13120 received 7 Sep 2005, last revised 2 Dec 2005},
  author={Kevin Fu and Seny Kamara and Tadayoshi Kohno},