Abstract
We give the first solution to the problem of access control in an arbitrary n-node hierarchy G (e.g., RBAC) where all of the following hold: (i) only hash functions are used for a node to derive a descendant's key from its own key, as opposed to the use of RSA public-key cryptography in many previous schemes (which requires slow modular exponentiations); (ii) the space complexity of the public information is the same as that of storing graph G (which is asymptotically optimal), as opposed to the quadratic space complexity of some other schemes; (iii) the derivation by a node of a descendant's access key takes O(n) bit operations in the worst case, as opposed to O(n^2) bit operations in some of the previous schemes; (iv) updates are handled locally in the hierarchy and do not "propagate" to
descendants or ancestors of the affected part of the tree; and (v) the scheme is resistant to collusion in that no subset of nodes can conspire to gain access to any node that is not already a descendant of one of the conspirators (hence legally accessible). Similar to a number of previous schemes, the private information at a node consists of a single key associated with that node. The security of our scheme relies on the existence of cryptographic one-way hash functions and the random oracle model. Another (more minor) property of our scheme is that it does not require access graph G to be free of directed cycles. We provide simple modifications to our scheme so it can handle Crampton's extensions of the standard hierarchies to "limited depth" and reverse inheritance.
