Secure Key-Updating for Lazy Revocation

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.

A condensed version of this paper has appeared in "Computer Security - ESORICS 2006," Lecture Notes in Computer Science, Vol. 4189, D. Gollmann, J. Meier, A. Sabelfeld (Eds.) (Springer, 2006) pp. 327-346.