Anonymous Hierarchical Key Assignment Schemes
Abstract
Hierarchical Key Assignment Schemes (HKAS) are cryptographic tools that enforce access control in partially ordered hierarchies, allowing each class to derive the keys of all classes below it. All existing schemes assume that the hierarchy structure is publicly known. In many modern applications, however, the topology of the access hierarchy is itself sensitive information that should be protected. We study the problem of extending existing HKAS to hide the hierarchy topology from adversaries who corrupt a subset of classes, without redesigning the underlying schemes from scratch. We formalize this goal through new security definitions capturing graph-hiding and topology privacy, and we propose a simple generic compiler that transforms any HKAS satisfying a natural anonymizability condition into one that achieves these stronger guarantees. Our main technical contribution is the identification of this condition, which requires that the joint distribution of the public values of the scheme be computationally indistinguishable from independently simulated random values. We show that this condition is not implied by the standard indistinguishability (IND-ST) security notion alone, by exhibiting a concrete counterexample based on the Akl-Taylor scheme. On the positive side, we verify that the Encryption Based Construction (EBC) and the Dynamic Encryption Based Construction (DEBC) of De Santis et al. both satisfy our condition and can therefore be made topology-private through our lightweight transformation.
