Author
M. Atallah, M. Blanton, N. Fazio, and K. Frikken
Abstract
Hierarchies arise in the context of access control whenever the user population can be modeled as a set of partially ordered classes (represented as a directed graph). A user with access privileges for a class obtains access to objects stored at that class and all descendant classes in the hierarchy. The problem of key management for such hierarchies then consists in assigning a key to each class in the hierarchy so that keys for descendant classes can be obtained via an efficient key derivation process.
We propose a solution to this problem with the following properties: (i) the space complexity of the public information is the same as that of storing the hierarchy; (ii) the private information at a class consists of a single key associated with that class; (iii) updates (i.e., revocations and additions) are handled locally in the hierarchy; (iv) the scheme is provably secure against collusion; and (v) each node can derive the key of any of its descendant with a number of symmetric-key operations bounded by the length of the path between the nodes. Whereas many previous schemes had some of these properties, ours is the first that satisfies all of them. The security of our scheme is based on pseudo-random functions, without reliance on the Random Oracle Model.
Another substantial contribution of this work is that for trees, we achieve a worst- and average-case key-derivation time that is exponentially better than the depth of a balanced hierarchy (double-exponentially better if the hierarchy is unbalanced, i.e., "tall and skinny"). This is obtained at the cost of only a constant factor in the space to store the hierarchy. We also show how to extend our techniques to more general hierarchies.
Finally, by making simple modifications to our scheme, we show how to handle extensions proposed by Crampton [2003] of the standard hierarchies to "limited depth" and reverse inheritance.
