Heuristics for Improving Cryptographic Key Assignment in a Hierarchy

In hierarchical distributed systems, shared data access can be controlled by assigning user groups single cryptographic keys that allow high level users derive low level keys, but not the reverse. The drawback in this approach to key management is the requirement of replacing keys throughout the entire hierarchy whenever group membership changes, to preserve security. This paper presents two algorithms, based on a precedence tree graph model, that use a distance-based heuristic to minimize the cost of key assignment and replacement, respectively. In the average case, only the keys belonging to the group affected and its sub-tree are replaced. A complexity analysis and experimental results indicating performance improvements demonstrate the feasibility of the proposed algorithms.