Cryptology ePrint Archive: Report 2005/334

Secure Key-Updating for Lazy Revocation

Michael Backes and Christian Cachin and Alina Oprea

Abstract: We consider the problem of efficient key management and user revocation in cryptographic file systems that allow shared access to files. A performance-efficient solution to user revocation in such systems is lazy revocation, a method that delays the re-encryption of a file until the next write to that file. We formalize the notion of key-updating schemes for lazy revocation, an abstraction to manage cryptographic keys in file systems with lazy revocation, and give a security definition for such schemes. We give two composition methods that combine two secure key-updating schemes into a new secure scheme that permits a larger number of user revocations. We prove the security of two slightly modified existing constructions and propose a novel binary tree construction that is also provable secure in our model. Finally, we give a systematic analysis of the computational and communication complexity of the three constructions and show that the novel construction improves the previously known constructions.

Category / Keywords: applications / key scheduling, secure storage, lazy revocation

Date: received 25 Sep 2005

Contact author: cca at zurich ibm com

Available formats: Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

Version: 20050925:125306 (All versions of this report)

Discussion forum: Show discussion | Start new discussion