Cryptology ePrint Archive: Report 2005/303

Key Regression: Enabling Efficient Key Distribution for Secure Distributed Storage

Kevin Fu and Seny Kamara and Tadayoshi Kohno

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.

Category / Keywords: Key regression, key rotation, lazy revocation, key distribution, content distribution network, hash chain, security proofs.

Publication Info: An extended abstract of this paper appears in ISOC Network and Distributed System Security Symposium (NDSS), February 2006. This is the full version.

Date: received 7 Sep 2005, last revised 2 Dec 2005

Contact author: kevinfu at cs umass edu

Available format(s): PDF | BibTeX Citation

Version: 20051203:022846 (All versions of this report)

Short URL: ia.cr/2005/303

Discussion forum: Show discussion | Start new discussion