A hierarchical key assignment scheme is an algorithm for assigning cryptographic keys to users. Consider a set of users that needs to communicate securely. Using the assigned secret key and public information, a user should be able to compute the key of any user that is lower in the partially ordered hierarchy.

There are two main contributions of this paper. First is the addition of the time parameter to the problem. Assigned keys have a limited life. Second is the provision of formal security proofs. The two security goals considered are key indistinguishability and key recovery.

Two types of adversaries are considered: static and adaptive. A static adversary is given access to all public information and the private information of every user who is not allowed to compute the key under attack. “An adaptive adversary is [given access to] all public information as well as all private information of a number of users of its choice.” There is a proof that these types of adversaries are equivalent (in polynomial time), so only static adversaries need to be considered.

The naive approach to “a time-bound hierarchical key assignment scheme [is] obtained by applying an [ordinary] key assignment scheme ... to each time period.” This approach has three drawbacks. First, users need to store a private key for each time period. Second, the amount of public information depends on both the number of hierarchical classes and the number of time periods. Third, “the key derivation procedure is expensive.”

The authors present two key assignment schemes. The first, a two-level encryption-based construction (TLEBC), addresses the first and third drawbacks, mentioned above. The second key assignment scheme, a two-level pairing-based construction (TLPBC), addresses the second and third drawbacks. The existence of a time-based hierarchical key assignment scheme that addresses all three drawbacks at the same time remains an open problem.

The paper has an extensive bibliography and a table comparing the computational complexity of the presented schemes with a few others in the literature. The definitions and mathematical proofs used are complex.