##
Dynamic and Efficient Key Management for Access Hierarchies

** Authors:** *
Mikhail Atallah,
Marina Blanton,
N. Fazio, and
Keith 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 of assigning a
key to each class in the hierarchy so that keys for descendant classes
can be obtained via efficient key derivation.

We propose a solution to this problem with the following properties:
(1) the space complexity of the public information is the same as that
of storing the hierarchy; (2) the private information at a class
consists of a single key associated with that class; (3) updates
(i.e., revocations and additions) are handled locally in the
hierarchy; (4) the scheme is provably secure against collusion; and
(5) 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 pseudorandom functions, without reliance on
the Random Oracle Model.

Another substantial contribution of this work is that we are able to
lower the key derivation time at the expense of modestly increasing
the public storage associated with the hierarchy. Inser- tion of
additional, so-called shortcut, edges, allows to lower the key
derivation to a small constant number of steps for graphs that are
total orders and trees by increasing the total number of edges by a
small asymptotic factor such as O(log* n) for an n-node hierarchy. For
more general access hierarchies of dimension d, we use a technique
that consists of adding dummy nodes and dimen- sion reduction. The key
derivation work for such graphs is then linear in d and the increase
in the number of edges is by the factor O(log^{d-1} n) compared to the
one-dimensional case.

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.

** Publication Info:**

ACM Transactions on Information and System Security (TISSEC), Vol. 12,
No. 3, Jan. 2009.

** Download: **
[pdf]
[bibtex entry]

Copyright © Nelly Fazio