Managing key hierarchies for access control enforcement : heuristic approaches

Data outsourcing is emerging today as a successful paradigm allowing individuals and organizations to resort to external servers for storing their data, and sharing them with others. The main problem of this trend is that sensitive data are stored on a site that is not under the data owner's direct control. This scenario poses a major security problem since often the external server is relied upon for ensuring high availability of the data, but it is not authorized to read them. Data need therefore to be encrypted. In such a context, the application of an access control policy requires different data to be encrypted with different keys so to allow the external server to directly enforce access control and support selective dissemination and access. The problem therefore emerges of designing solutions for the efficient management of an encryption policy enforcing access control, with the goal of minimizing the number of keys to be maintained by the system and distributed to users. In this paper, we prove that the problem of minimizing the number of keys is NP-hard and present alternative approaches for its solution. We first formulate the minimization problem as an instance of an integer linear programming problem and then propose three different families of heuristics, which are based on a key derivation tree exploiting the relationships among user groups. Finally, we experimentally evaluate the performance of our heuristics, comparing them with previous approaches.