Abstract
The problem of key management in access hierarchies studies ways
to assign keys to users and classes such that each user, after receiving her secret
key(s), is able to independently compute access keys for (and thus obtain access
to) the appropriate resources defined by the hierarchical structure. If user privi-
leges additionally are time-based, the key(s) a user receives should permit access
to the resources only at the appropriate times. This paper presents a new, prov-
ably secure, and efficient solution that can be used to add time-based capabilities
to existing hierarchical schemes. It achieves the following performance bounds:
(i) to be able to obtain access to an arbitrary contiguous set of time intervals, a
user is required to store at most 3 keys; (ii) the keys for a user can be computed by
the system in constant time; (iii) key derivation by the user within the authorized
time intervals involves a small constant number of inexpensive cryptographic op-
erations; and (iv) if the total number of time intervals in the system is n, then the
server needs to maintain public storage larger than n by only a small asymptotic
factor, e.g., O(log
∗
n log log n) with a small constant.
