International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: Secure Key-Updating for Lazy Revocation

Michael Backes
Christian Cachin
Alina Oprea
Search ePrint
Search Google
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.
  title={Secure Key-Updating for Lazy Revocation},
  booktitle={IACR Eprint archive},
  keywords={applications / key scheduling, secure storage, lazy revocation},
  note={ 13051 received 25 Sep 2005},
  author={Michael Backes and Christian Cachin and Alina Oprea},