Paper 2005/334

Secure Key-Updating for Lazy Revocation

Michael Backes, Christian Cachin, and Alina Oprea


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.

Available format(s)
Publication info
Published elsewhere. Unknown where it was published
key schedulingsecure storagelazy revocation
Contact author(s)
cca @ zurich ibm com
2005-09-25: received
Short URL
Creative Commons Attribution


      author = {Michael Backes and Christian Cachin and Alina Oprea},
      title = {Secure Key-Updating for Lazy Revocation},
      howpublished = {Cryptology ePrint Archive, Paper 2005/334},
      year = {2005},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.