Dynamic and Efficient Key Management for Access Hierarchies

Get BibTex-formatted data

Download

PDF

Author

M. Atallah, K. Frikken, and M. Blanton

Tech report number

CERIAS TR 2006-02

Entry type

inproceedings

Abstract

The problem of key management in an access hierarchy has elicited much interest in the literature. The hierarchy is modeled as a set of partially ordered classes (represented as a directed graph), and a user who obtains access (i.e., a key) to a certain class can also obtain access to all descendant classes of her class through key derivation. Our solution to the above problem has the following properties: (i) only hash functions are used for a node to derive a descendant's key from its own key; (ii) the space complexity of the public information is the same as that of storing the hierarchy; (iii) the private information at a class consists of a single key associated with that class; (iv) updates (revocations, additions, etc.) are handled locally in the hierarchy; (v) the scheme is provably secure against collusion; and (vi) key derivation by a node of its descendant's key is bounded by the number of bit operations linear in 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. Moreover, for trees (and other "recursively decomposable" hierarchies), we are the first to achieve a worst- and average-case number of bit operations for key derivation that is exponentially better than the depth of a balanced hierarchy (double-exponentially better if the hierarchy is unbalanced, i.e., "tall and skinny"); this is achieved with only a constant increase in the space for the hierarchy. We also show how with simple modifications our scheme can handle extensions proposed by Crampton of the standard hierarchies to "limited depth" and reverse inheritance. The security of our scheme relies only on the use of pseudo-random functions.

Download

PDF

Date

2005 – 11

Address

New York, NY, USA

Booktitle

ACM Conference on Computer and Communications Security (CCS)

Key alpha

atallah

Pages

190--201

Publisher

ACM Press

Affiliation

Purdue University

Publication Date

2005-11-01

Isbn

1-59593-226-7

Keywords

derivation, efficient key, hierarchical access control, key management

Language

English

BibTex-formatted data

To refer to this entry, you may select and copy the text below and paste it into your BibTex document. Note that the text may not contain all macros that BibTex supports.

@Inproceedings{ atallah,
	title = "Dynamic and Efficient Key Management for Access Hierarchies",
	author = "M. Atallah, K. Frikken, and M. Blanton",
	year = "2005",
	month = "11",
	address = "New York, NY, USA",
	booktitle = "ACM Conference on Computer and Communications Security  (CCS)",
	pages = "190--201",
	publisher = "ACM Press",
	abstract = "The problem of key management in an access hierarchy has elicited much interest in the literature. The hierarchy is modeled as a set of partially ordered classes (represented as a directed graph), and a user who obtains access (i.e., a key) to a certain class can also obtain access to all descendant classes of her class through key derivation. Our solution to the above problem has the following properties: (i) only hash functions are used for a node to derive a descendant's key from its own key; (ii) the space complexity of the public information is the same as that of storing the hierarchy; (iii) the private information at a class consists of a single key associated with that class; (iv) updates (revocations, additions, etc.) are handled locally in the hierarchy; (v) the scheme is provably secure against collusion; and (vi) key derivation by a node of its descendant's key is bounded by the number of bit operations linear in 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. Moreover, for trees (and other "recursively decomposable" hierarchies), we are the first to achieve a worst- and average-case number of bit operations for key derivation that is exponentially better than the depth of a balanced hierarchy (double-exponentially better if the hierarchy is unbalanced, i.e., "tall and skinny"); this is achieved with only a constant increase in the space for the hierarchy. We also show how with simple modifications our scheme can handle extensions proposed by Crampton of the standard hierarchies to "limited depth" and reverse inheritance. The security of our scheme relies only on the use of pseudo-random functions.",
	affiliation = "Purdue University",
	isbn = "1-59593-226-7",
	keywords = " derivation,  efficient key,  hierarchical access control,  key management",
	language = "English",
}