More Web Proxy on the site http://driver.im/

Article

Dynamic and efficient key management for access hierarchies

Authors:

Mikhail J. Atallah,

Keith B. Frikken,

Marina BlantonAuthors Info & Claims

CCS '05: Proceedings of the 12th ACM conference on Computer and communications security

Pages 190 - 202

https://doi.org/10.1145/1102120.1102147

Published: 07 November 2005 Publication History

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 [13]. The security of our scheme relies only on the use of pseudo-random functions.

References

[1]

S. Akl and P. Taylor. Cryptographic solution to a problem of access control in a hierarchy. ACM Transactions on Computer Systems, 1(3):239--248, September 1983.

Digital Library

[2]

R. Anderson and M. Kuhn. Tamper resistance - a cautionary note. In USENIX Workshop on Electronic Commerce, pages 1--11, November 1996.

Digital Library

[3]

R. Anderson and M. Kuhn. Low cost attacks on tamper resistant devices. In Security Protocols Workshop, volume 1361 of LNCS, pages 125--136, April 1997.

Digital Library

[4]

D. Bell and L. LaPadula. Secure computer systems: Mathematical foundations. Technical Report MTR-2547, MITRE Corporation, March 1973.

[5]

J. Birget, X. Zou, G. Noubir, and B. Ramamurthy. Hierarchy-based access control in distributed environments. In ICC Conference 2001, June 2001.

[6]

C. Chang and D. Buehrer. Access control in a hierarchy using a one-way trapdoor function. Computers and Mathematics with Applications, 26(5):71--76, 1993.

[7]

C. Chang, I. Lin, H. Tsai, H. Wang, and T. Taichung. A key assignment scheme for controlling access in partially ordered user hierarchies. In International Conference on Advanced Information Networking and Application (AINA'04), 2004.

Digital Library

[8]

T. Chen and Y Chung. Hierarchical access control based on chinese remainder theorem and symmetric algorithm. Computers & Security, 2002.

Digital Library

[9]

T. Chen, Y. Chung, and C. Tian. A novel key management scheme for dynamic access control in a user hierarchy. In IEEE Annual International Computer Software and Applications Conference (COMPSAC'04), pages 396--401, September 2004.

Digital Library

[10]

G. Chick and S. Tavares. Flexible access control with master keys. In Advances in Cryptology - CRYPTO'89, volume 435 of LNCS, pages 316--322, 1990.

Digital Library

[11]

H. Chien and J. Jan. New hierarchical assignment without public key cryptography. Computers & Security, 22(6):523--526, 2003.

Digital Library

[12]

J. Chou, C. Lin, and T. Lee. A novel hierarchical key management scheme based on quadratic residues. In Internation Symposium on Parallel and Distributed Processing and Applications (ISPA'04), volume 3358, pages 858--865, December 2004.

Digital Library

[13]

J. Crampton. On permissions, inheritance and role hierarchies. In ACM Conference on Computer and Communications Security (CCS), pages 85--92, October 2003.

Digital Library

[14]

M. Das, A. Saxena, V. Gulati, and D. Phatak. Hierarchical key management scheme using polynomial interpolation. ACM SIGOPS Operating Systems Review, 39(1):40--47, January 2005.

Digital Library

[15]

D. Denning, S. Akl, M. Morgenstern, and P. Neumann. Views for multilevel database security. In IEEE Symposium on Security and Privacy, pages 156--172, April 1986.

[16]

D. Ferraiolo and D. Kuhn. Role based access control. In National Computer Security Conference, 1992.

[17]

A. Ferrara and B. Masucci. An information-theoretic approach to the access control problem. In Italian Conference on Theoretical Computer Science (ICTCS'03), volume 2841, pages 342--354, October 2003.

[18]

L. Fraim. Scomp: a solution to multilevel security problem. IEEE Computer, 16(7):126--143, July 1983.

Digital Library

[19]

J. Gilbert, J. Hutchinson, and R. Tarjan. A separation theorem for graphs of bounded genus. Journal of Algorithms, 5:391--407, 1984.

Digital Library

[20]

M. Goodrich. Planar separators and parallel polygon triangulation. In Annual ACM Symposium on Theory of Computing, pages 507--516, 1992.

Digital Library

[21]

L. Guibas, J. Hershberger, D. Leven, M. Sharir, and R. Tarjan. Linear time algorithms for visibility and shortest path problems inside simple polygons. In Annual ACM Symposium on Computational Geometry, pages 1--13, 1986.

Digital Library

[22]

L. Harn and H. Lin. A cryptographic key generation scheme for multilevel data security. Computers & Security, 9(6):539--546, October 1990.

Digital Library

[23]

M. He, P. Fan, F. Kaderali, and D. Yuan. Access key distribution scheme for level-based hierarchy. In International Conference on Parallel and Distributed Computing, Applications and Technologies (PDCAT'03), pages 942--945, August 2003.

[24]

H. Huang and C. Chang. A new cryptographic key assignment scheme with time-constraint access control in a hierarchy. Computer Standards & Interfaces, 26:159--166, 2004.

[25]

M. Hwang. An improvement of novel cryptographic key assignment scheme for dynamic access control in a hierarchy. IEICE Trans. Fundamentals, E82-A(2):548--550, March 1999.

[26]

M. Hwang. A new dynamic key generation scheme for access control in a hierarchy. Nordic Journal of Computing, 6(4):363--371, Winter 1999.

Digital Library

[27]

M. Hwang and W. Yang. Controlling access in large partially ordered hierarchies using cryptographic keys. Journal of Systems and Software, 67(2):99--107, August 2003.

Digital Library

[28]

D. Knuth. Sorting and Searching, volume 3 of The Art of Computer Programming. Addison-Wesley, 1973.

[29]

H. Liaw, S. Wang, and C. Lei. A dynamic cryptographic key assignment scheme in a tree structure. Computers and Mathematics with Applications, 25(6):109--114, 1993.

[30]

C. Lin. Hierarchical key assignment without public-key cryptography. Computers & Security, 20(7):612--619, 2001.

Digital Library

[31]

I. Lin, M. Hwang, and C. Chang. A new key assignment scheme for enforcing complicated access control policies in hierarchy. Future Generation Computer Systems, 19(4):457--462, 2003.

Digital Library

[32]

R. Lipton and R. Tarjan. A separator theorem for planar graphs. SIAM Journal Applied Mathemathics, 36:177--189, 1979.

[33]

W. Lu and M. Sundareshan. A moredle for multilevel security in computer networks. In INFOCOM'88, pages 1095--1104, 1988.

[34]

S. MacKinnon, P. Taylor, H. Meijer, and S. Akl. An optimal algorithm for assigning cryptographic keys to control access in a hierarchy. IEEE Transactions on Computers, 34(9):797--802, September 1985.

Digital Library

[35]

P. Maheshwari. Enterprise application integration using a component-based architecture. In IEEE Annual International Computer Software and Applications Conference (COMSAC'03), pages 557--563, 2003.

Digital Library

[36]

J. McHugh and A. Moore. A security policy and formal top level specification for a multi-level secure local area network. In IEEE Symposiom on Security and Privacy, pages 34--49, 1986.

[37]

K. Ohta, T. Okamoto, and K. Koyama. Membership authentication for hierarchical multigroups using the extended fiat-shamir scheme. In Workshop on the Theory and Application of Cryptographic Techniques on Advances in Cryptology, pages 446--457, February 1991.

Digital Library

[38]

I. Ray, I. Ray, and N. Narasimhamurthi. A cryptographic solution to implement access control in a hierarchy and more. In ACM Symposium on Access Control Models and Technologies, June 2002.

Digital Library

[39]

J. Rose and J. Gasteiger. Hierarchical classification as an aid to database and hit-list browsing. In International Conference on Information and Knowledge Management, pages 408--414, 1994.

Digital Library

[40]

R. Sandhu. On some cryptographic solutions for access control in a tree hierarchy. In Fall Joint Computer Conference on Exploring technology: today and tomorrow, pages 405--410, December 1987.

Digital Library

[41]

R. Sandhu, E. Coyne, H. Feinstein, and C. Youman. Role-based access control models. IEEE Computer, 29(2):38--47, 1996.

Digital Library

[42]

R.S. Sandhu. Cryptographic implementation of a tree hierarchy for access control. Information Processing Letters, 27(2):95--98, January 1988.

Digital Library

[43]

A. De Santis, A. Ferrara, and B. Masucci. Cryptographic key assignment schemes for any access control policy. Information Processing Letters (IPL), 92(4):199--205, November 2004.

Digital Library

[44]

V. Shen and T. Chen. A novel key management scheme based on discrete logarithms and polynomial interpolations. Computers & Security, 21(2):164--171, 2002.

Digital Library

[45]

Y. Sun and K. Liu. Scalable hierarchical access control in secure group communication. In IEEE INFOCOM 2004, 2004.

[46]

H. Tsai and C. Chang. A cryptographic implementation for dynamic access control in a user hierarchy. Computers & Security, 14(2):159--166, 1995.

Digital Library

[47]

W. Tzeng. A time-bound cryptographic key assignment scheme for access control in a hierarchy. IEEE Transactions on Knowledge and Data Engineering, 14(1):182--188, 2002.

Digital Library

[48]

J. Wu and R. Wei. An access control scheme for partially ordered set hierarchy with provable security. Cryptology ePrint Archive, Report 2004/295, 2004. http://eprint.iacr.org/.

[49]

T. Wu and C. Chang. Cryptograpic key assignment scheme for hierarchical access control. International Journal of Computer Systems Science and Engineering, 1(1):25--28, 2001.

[50]

J. Yeh, R. Chow, and R. Newman. A key assignment for enforcing access control policy exceptions. In International Symposium on Internet Technology, pages 54--59, 1998.

[51]

Q. Zhang and Y. Wang. A centralized key management scheme for hierarchical access control. In IEEE Global Telecommunications Conference (Globecom'04), 2004.

[52]

Y. Zheng, T. Hardjono, and J. Pieprzyk. Sibling intractable function families and their applications. In Advances in Cryptology - AsiaCrypt'91, LNCS, 1992.

Digital Library

[53]

Y. Zheng, T. Hardjono, and J. Seberry. New solutions to the problem of access control in a hierarchy. Technical report, 1993.

[54]

S. Zhong. A practical key management scheme for access control in a user hierarchy. Computers & Security, 21(8):750--759, 2002.

Digital Library

Cited By

Bacis EDe Capitani di Vimercati SForesti SParaboschi SRosa MSamarati P(2024)Mix&Slice for Efficient Access Revocation on Outsourced DataIEEE Transactions on Dependable and Secure Computing10.1109/TDSC.2023.328059021:3(1390-1405)Online publication date: May-2024
https://doi.org/10.1109/TDSC.2023.3280590
Celikbilek ICeliktas BOzdemir E(2024)A Hierarchical Key Assignment Scheme: A Unified Approach for Scalability and EfficiencyIEEE Access10.1109/ACCESS.2024.340184412(70568-70580)Online publication date: 2024
https://doi.org/10.1109/ACCESS.2024.3401844
Lal SKumar N(2022)An efficient flexible hierarchical access control scheme enabling real-life exceptionsSādhanā10.1007/s12046-021-01776-047:1Online publication date: 12-Jan-2022
https://doi.org/10.1007/s12046-021-01776-0
Show More Cited By

Index Terms

Dynamic and efficient key management for access hierarchies

Recommendations

Dynamic and Efficient Key Management for Access Hierarchies

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 ...
Secure key management scheme for dynamic hierarchical access control based on ECC

An access control mechanism in a user hierarchy is used to provide the management of sensitive information for authorized users. The users and their own information can be organized into a number of disjoint sets of security classes according to their ...
Key hierarchies for hierarchical access control in secure group communications

The problem of hierarchical access control in secure group communications has elicited much interest in the literatures. However, most of the researches to date on hierarchical access control pay more attention to the particular encryption techniques, ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

CCS '05: Proceedings of the 12th ACM conference on Computer and communications security

November 2005

422 pages

ISBN:1595932267

DOI:10.1145/1102120

General Chair:
Vijay Atluri
Rutgers University
,
Program Chairs:
Catherine Meadows
Naval Research Laboratory
,
Ari Juels
RSA Laboratories

Copyright © 2005 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 07 November 2005

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

CCS05

Sponsor:

CCS05: 12th ACM Conference on Computer and Communications Security 2005

November 7 - 11, 2005

VA, Alexandria, USA

Acceptance Rates

Overall Acceptance Rate 1,261 of 6,999 submissions, 18%

Upcoming Conference

CCS '25

Sponsor:
sigsac

ACM SIGSAC Conference on Computer and Communications Security

October 13 - 17, 2025

Taipei , Taiwan

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

133
Total Citations
View Citations
1,154
Total Downloads

Downloads (Last 12 months)8
Downloads (Last 6 weeks)2

Reflects downloads up to 05 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Bacis EDe Capitani di Vimercati SForesti SParaboschi SRosa MSamarati P(2024)Mix&Slice for Efficient Access Revocation on Outsourced DataIEEE Transactions on Dependable and Secure Computing10.1109/TDSC.2023.328059021:3(1390-1405)Online publication date: May-2024
https://doi.org/10.1109/TDSC.2023.3280590
Celikbilek ICeliktas BOzdemir E(2024)A Hierarchical Key Assignment Scheme: A Unified Approach for Scalability and EfficiencyIEEE Access10.1109/ACCESS.2024.340184412(70568-70580)Online publication date: 2024
https://doi.org/10.1109/ACCESS.2024.3401844
Lal SKumar N(2022)An efficient flexible hierarchical access control scheme enabling real-life exceptionsSādhanā10.1007/s12046-021-01776-047:1Online publication date: 12-Jan-2022
https://doi.org/10.1007/s12046-021-01776-0
Huang QZhang ZYang Y(2021)Privacy-Preserving Media Sharing with Scalable Access Control and Secure Deduplication in Mobile Cloud ComputingIEEE Transactions on Mobile Computing10.1109/TMC.2020.297070520:5(1951-1964)Online publication date: 1-May-2021
https://doi.org/10.1109/TMC.2020.2970705
Kapil GAgrawal AAttaallah AAlgarni AKumar RKhan R(2020)Attribute based honey encryption algorithm for securing big data: Hadoop distributed file system perspectivePeerJ Computer Science10.7717/peerj-cs.2596(e259)Online publication date: 17-Feb-2020
https://doi.org/10.7717/peerj-cs.259
Jaswal SMalhotra M(2019)Identification of Various Privacy and Trust Issues in Cloud Computing EnvironmentCloud Security10.4018/978-1-5225-8176-5.ch051(992-1013)Online publication date: 2019
https://doi.org/10.4018/978-1-5225-8176-5.ch051
Kumar NMathuria A(2019)Comprehensive evaluation of key management hierarchies for outsourced dataCybersecurity10.1186/s42400-019-0026-y2:1Online publication date: 19-Feb-2019
https://doi.org/10.1186/s42400-019-0026-y
Pareek GPurushothama B(2019)Extended hierarchical key assignment scheme (E-HKAS): how to efficiently enforce explicit policy exceptions in dynamic hierarchiesSādhanā10.1007/s12046-019-1216-844:12Online publication date: 16-Nov-2019
https://doi.org/10.1007/s12046-019-1216-8
Jaswal SMalhotra M(2018)Identification of Various Privacy and Trust Issues in Cloud Computing EnvironmentCritical Research on Scalability and Security Issues in Virtual Cloud Environments10.4018/978-1-5225-3029-9.ch005(95-121)Online publication date: 2018
https://doi.org/10.4018/978-1-5225-3029-9.ch005
Zhang XHan J(2018)Research on Key Management Scheme for Dynamic Revocable Key-Aggregate Cryptosystem2018 IEEE 4th International Conference on Computer and Communications (ICCC)10.1109/CompComm.2018.8780727(1904-1908)Online publication date: Dec-2018
https://doi.org/10.1109/CompComm.2018.8780727
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents