Paper 2005/303

Key Regression: Enabling Efficient Key Distribution for Secure Distributed Storage

Kevin Fu, Seny Kamara, and Tadayoshi Kohno


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.

Available format(s)
Publication info
Published elsewhere. An extended abstract of this paper appears in ISOC Network and Distributed System Security Symposium (NDSS), February 2006. This is the full version.
Key regressionkey rotationlazy revocationkey distributioncontent distribution networkhash chainsecurity proofs.
Contact author(s)
kevinfu @ cs umass edu
2005-12-03: last of 5 revisions
2005-09-07: received
See all versions
Short URL
Creative Commons Attribution


      author = {Kevin Fu and Seny Kamara and Tadayoshi Kohno},
      title = {Key Regression: Enabling Efficient Key Distribution for Secure Distributed Storage},
      howpublished = {Cryptology ePrint Archive, Paper 2005/303},
      year = {2005},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.