Dynamic and Efficient Key Management for Access Hierarchies
Dynamic and Efficient Key Management for Access Hierarchies
复制标题
DOI：
10.1145/1455526.1455531
复制
发表时间：
2009-01-01
影响因子：
--
通讯作者：
Frikken, Keith B.
中科院分区：
文献类型：
--
作者：
Atallah, Mikhail J.;Blanton, Marina;Frikken, Keith B.
在访问控制的上下文中，每当用户群体可以被建模为一组部分有序的类（表示为有向图）时，就会出现层次结构。具有类访问权限的用户可以访问存储在该类和层次结构中的所有子类中的对象。对于这种层次结构的密钥管理问题，我们提出了一种解决方案，它具有以下性质：（1）公共信息的空间复杂度与存储层次结构的空间复杂度相同;（2）类处的私有信息由与该类相关联的单个密钥组成;（3）更新（即，简化和添加）在层次结构中本地处理;（4）该方案可证明是安全的，不会发生共谋;（5）每个节点都可以通过节点之间路径长度限制的多个密钥操作来导出其任何后代的密钥。虽然许多以前的计划有一些这些性质，我们是第一个满足所有这些。我们的方案的安全性是基于伪随机函数，而不依赖于随机预言模型。这项工作的另一个重要贡献是，我们能够降低密钥推导时间的代价是适度增加与层次结构相关的公共存储。插入额外的所谓捷径边，可以通过将边的总数增加一个小的渐进因子（例如O（log* n）），将密钥推导降低到全阶和树图的小常数步骤数。n节点层次结构。对于更一般的访问层次结构的维度d，我们使用的技术，包括添加虚拟节点和降维。这样的图的密钥推导工作，然后是线性的d和增加的边的数量是由因子O（log（d-1）n）相比，一维的case.Finally，通过简单的修改，我们的计划，我们展示了如何处理Crampton [2003]提出的标准层次结构的扩展到“有限的深度”和反向继承。
Hierarchies arise in the context of access control whenever the user population can be modeled as a set of partially ordered classes ( represented as a directed graph). A user with access privileges for a class obtains access to objects stored at that class and all descendant classes in the hierarchy. The problem of key management for such hierarchies then consists of assigning a key to each class in the hierarchy so that keys for descendant classes can be obtained via efficient key derivation.We propose a solution to this problem with the following properties: (1) the space complexity of the public information is the same as that of storing the hierarchy; (2) the private information at a class consists of a single key associated with that class; (3) updates (i.e., revocations and additions) are handled locally in the hierarchy; (4) the scheme is provably secure against collusion; and (5) each node can derive the key of any of its descendant with a number of symmetric-key operations bounded by the length of the path between the nodes. Whereas many previous schemes had some of these properties, ours is the first that satisfies all of them. The security of our scheme is based on pseudorandom functions, without reliance on the Random Oracle Model.Another substantial contribution of this work is that we are able to lower the key derivation time at the expense of modestly increasing the public storage associated with the hierarchy. Insertion of additional, so-called shortcut, edges, allows to lower the key derivation to a small constant number of steps for graphs that are total orders and trees by increasing the total number of edges by a small asymptotic factor such as O(log* n) for an n-node hierarchy. For more general access hierarchies of dimension d, we use a technique that consists of adding dummy nodes and dimension reduction. The key derivation work for such graphs is then linear in d and the increase in the number of edges is by the factor O(log(d-1) n) compared to the one-dimensional case.Finally, by making simple modifications to our scheme, we show how to handle extensions proposed by Crampton [2003] of the standard hierarchies to "limited depth" and reverse inheritance.