Dynamic and Efficient Key Management for Access Hierarchies

ABSTRACT

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.

REFERENCES

• 1: Selim G. Akl , Peter D. Taylor, Cryptographic solution to a problem of access control in a hierarchy, ACM Transactions on Computer Systems (TOCS), v.1 n.3, p.239-248, August 1983 [doi>10.1145/357369.357372]
• 2: Alon, N. and Schieber, B. 1987. Optimal preprocessing for answering on-line product queries. Tech. rep. TR 71/87, Institute of Computer Science, Tel-Aviv University.
• 3: Ross Anderson , Markus Kuhn, Tamper resistance: a cautionary note, Proceedings of the 2nd conference on Proceedings of the Second USENIX Workshop on Electronic Commerce, p.1-1, November 18-21, 1996, Oakland, California
• 4: Ross J. Anderson , Markus G. Kuhn, Low Cost Attacks on Tamper Resistant Devices, Proceedings of the 5th International Workshop on Security Protocols, p.125-136, April 07-09, 1997
• 5: Mikhail J. Atallah , Keith B. Frikken , Marina Blanton, Dynamic and efficient key management for access hierarchies, Proceedings of the 12th ACM conference on Computer and communications security, November 07-11, 2005, Alexandria, VA, USA [doi>10.1145/1102120.1102147]
• 6: Bell, D. and LaPadula, L. 1973. Secure computer systems: Mathematical foundations. Tech. rep. MTR--2547, MITRE Corporation.
• 7: Mihir Bellare , Ran Canetti , Hugo Krawczyk, Keying Hash Functions for Message Authentication, Proceedings of the 16th Annual International Cryptology Conference on Advances in Cryptology, p.1-15, August 18-22, 1996
• 8: Birget, J., Zou, X., Noubir, G., and Ramamurthy, B. 2001. Hierarchy-based access control in distributed environments. In Proceedings of the IEEE International Conference on Communications (ICC’01). 229--233.
• 9: Hans L. Bodlaender , Gerard Tel , Nicola Santoro, Trade-offs in non-reversing diameter, Nordic Journal of Computing, v.1 n.1, p.111-134, Spring 1994
• 10: Chang, C. and Buehrer, D. 1993. Access control in a hierarchy using a one-way trapdoor function. Comput. Math. Appl. 26, 5, 71--76.
• 11: Chin-Chen Chang , Iuon-Chang Lin , Hui-Min Tsai , Hsiao-Hsi Wang, A Key Assignment Scheme for Controlling Access in Partially Ordered User Hierarchies, Proceedings of the 18th International Conference on Advanced Information Networking and Applications, p.376, March 29-31, 2004
• 12: Chazelle, B. 1987. Computing on a free tree via complexity-preserving mappings. Algorithmica 2, 337--361.
• 13: Chen, T. and Chung, Y. 2002. Hierarchical access control based on Chinese remainder theorem and symmetric algorithm. Comput. Secur. 565--570.
• 14: Tzer-Shyong Chen , Yu-Fang Chung , Chang-Sin Tian, A Novel Key Management Scheme for Dynamic Access Control in a User Hierarchy, Proceedings of the 28th Annual International Computer Software and Applications Conference, p.396-397, September 28-30, 2004
• 15: Gerald C. Chick , Stafford E. Tavares, Flexible Access Control with Master Keys, Proceedings of the 9th Annual International Cryptology Conference on Advances in Cryptology, p.316-322, August 20-24, 1989
• 16: Chien, H. and Jan, J. 2003. New hierarchical assignment without public key cryptography. Comput. Secur. 22, 6, 523--526.
• 17: Chou, J., Lin, C., and Lee, T. 2004. A novel hierarchical key management scheme based on quadratic residues. In Proceedings of the International Symposium on Parallel and Distributed Processing and Applications (ISPA’04). Vol. 3358. 858--865.
• 18: Ronald Cramer , Victor Shoup, Design and Analysis of Practical Public-Key Encryption Schemes Secure against Adaptive Chosen Ciphertext Attack, SIAM Journal on Computing, v.33 n.1, p.167-226, 2004 [doi>10.1137/S0097539702403773]
• 19: Jason Crampton, On permissions, inheritance and role hierarchies, Proceedings of the 10th ACM conference on Computer and communications security, October 27-30, 2003, Washington D.C., USA [doi>10.1145/948109.948123]
• 20: Manik Lal Das , Ashutosh Saxena , Ved P. Gulati , Deepak B. Phatak, Hierarchical key management scheme using polynomial interpolation, ACM SIGOPS Operating Systems Review, v.39 n.1, p.40-47, January 2005 [doi>10.1145/1044552.1044556]
• 21: De Santis, A., Ferrara, A., and Masucci, B. 2007. Efficient provably-secure hierarchical key assignment schemes. In Proceedings of the International Symposium on Mathematical Foundations of Computer Science (MFCS’07). Lecture Notes on Computer Science, vol. 4708. 371--382.
• 22: Denning, D., Akl, S., Morgenstern, M., and Neumann, P. 1986. Views for multilevel database security. In Proceedings of the IEEE Symposium on Security and Privacy (SP’86). 156--172.
• 23: Yevgeniy Dodis , Nelly Fazio , Aggelos Kiayias , Moti Yung, Scalable public-key tracing and revoking, Distributed Computing, v.17 n.4, p.323-347, May 2005 [doi>10.1007/s00446-004-0120-5]
• 24: Dushnik, B. and Miller, E. 1941. Partially ordered sets. American Journal of Mathematics 63, 600--610.
• 25: Michael Elkin , David Peleg, Approximating k-spanner problems for k > 2, Theoretical Computer Science, v.337 n.1-3, p.249-277, 9 June 2005 [doi>10.1016/j.tcs.2004.11.022]
• 26: Ferraiolo, D. and Kuhn, D. 1992. Role based access control. In Proceedings of the National Computer Security Conference (NISSC’92). 554--563.
• 27: Ferrara, A. and Masucci, B. 2003. An information-theoretic approach to the access control problem. In Proceedings of the Italian Conference on Theoretical Computer Science (ICTCS’03). vol. 2841. 342--354.
• 28: L. J. Fraim, Scomp: A Solution to the Multilevel Security Problem, Computer, v.16 n.7, p.26-34, July 1983 [doi>10.1109/MC.1983.1654440]
• 29: Oded Goldreich, Foundations of Cryptography: Volume 2, Basic Applications, Cambridge University Press, New York, NY, 2004
• 30: Dov Harel , Robert Endre Tarjan, Fast algorithms for finding nearest common ancestors, SIAM Journal on Computing, v.13 n.2, p.338-355, May 1984 [doi>10.1137/0213024]
• 31: L. Harn , H.-Y. Lin, A cryptographic key generation scheme for multilevel data security, Computers and Security, v.9 n.6, p.539-546, Oct. 1990 [doi>10.1016/0167-4048(90)90132-D]
• 32: He, M., Fan, P., Kaderali, F., and Yuan, D. 2003. Access key distribution scheme for level-based hierarchy. In Proceedings of the International Conference on Parallel and Distributed Computing, Applications and Technologies (PDCAT’03). 942--945.
• 33: Huang, H. and Chang, C. 2004. A new cryptographic key assignment scheme with time-constraint access control in a hierarchy. Comput. Stand. Interfaces 26, 159--166.
• 34: Hwang, M. 1999a. An improvement of novel cryptographic key assignment scheme for dynamic access control in a hierarchy. IEICE Trans. Fundam. E82--A, 2 (Mar.), 548--550.
• 35: Min-Shiang Hwang, A new dynamic key generation scheme for access control in a hierarchy, Nordic Journal of Computing, v.6 n.4, p.363-371, Winter 1999
• 36: Min-Shiang Hwang , Wei-Pang Yang, Controlling access in large partially ordered hierarchies using cryptographic keys, Journal of Systems and Software, v.67 n.2, p.99-107, 15 August 2003 [doi>10.1016/S0164-1212(02)00091-2]
• 37: Liaw, H., Wang, S., and Lei, C. 1993. A dynamic cryptographic key assignment scheme in a tree structure. Comput. Math. Appl. 25, 6, 109--114.
• 38: Lin, C. 2001. Hierarchical key assignment without public-key cryptography. Comput. Secur. 20, 7, 612--619.
• 39: Iuon-Chang Lin , Min-Shiang Hwang , Chin-Chen Chang, A new key assignment scheme for enforcing complicated access control policies in hierarchy, Future Generation Computer Systems, v.19 n.4, p.457-462, May 2003 [doi>10.1016/S0167-739X(02)00200-5]
• 40: Lu, W. and Sundareshan, M. 1988. A moredle for multilevel security in computer networks. In Proceedings of the Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM’88). 1095--1104.
• 41: Stephen J. MacKinnon , Peter D. Taylor , Henk Meijer , Selim G. Akl, An Optimal Algorithm for Assigning Cryptographic Keys to Control Access in a Hierarchy, IEEE Transactions on Computers, v.34 n.9, p.797-802, September 1985 [doi>10.1109/TC.1985.1676635]
• 42: Piyush Maheshwari, Enterprise Application Integration using a Component-based Architecture, Proceedings of the 27th Annual International Conference on Computer Software and Applications, p.557, November 03-06, 2003
• 43: McHugh, J. and Moore, A. 1986. A security policy and formal top level specification for a multi-level secure local area network. In Proceedings of the IEEE Symposium on Security and Privacy (SP’86). 34--49.
• 44: Kazuo Ohta , Tatsuaki Okamoto , Kenji Koyama, Membership authentication for hierarchical multigroups using the extended Fiat-Shamir scheme, Proceedings of the workshop on the theory and application of cryptographic techniques on Advances in cryptology, p.446-457, February 1991, Aarhus, Denmark
• 45: Overmars, M. and van Leeuwen, J. 1981a. Dynamization of order decomposable set problems. J. Algorithms 2, 3, 245--260.
• 46: Overmars, M. and van Leeuwen, J. 1981b. Maintenance of configurations in the plane. J. Comput. Syst. Sci. 23, 2, 166--204.
• 47: Peleg, D. and Schaeffer, A. 1989. Graph spanners. Theor. Comput. Sci. 13, 99--116.
• 48: Indrakshi Ray , Indrajit Ray , Natu Narasimhamurthi, A cryptographic solution to implement access control in a hierarchy and more, Proceedings of the seventh ACM symposium on Access control models and technologies, June 03-04, 2002, Monterey, California, USA [doi>10.1145/507711.507723]
• 49: J. Royce Rose , Johann Gasteiger, Hierarchical classification as an aid to database and hit-list browsing, Proceedings of the third international conference on Information and knowledge management, p.408-414, November 29-December 02, 1994, Gaithersburg, Maryland, United States [doi>10.1145/191246.191315]
• 50: R. S. Sandhu, On some cryptographic solutions for access control in a tree hierarchy, Proceedings of the 1987 Fall Joint Computer Conference on Exploring technology: today and tomorrow, p.405-410, December 1987, Dallas, Texas, United States
• 51: Ravinderpal S. Sandhu, Cryptographic implementation of a tree hierarchy for access control, Information Processing Letters, v.27 n.2, p.95-98, February 29, 1988 [doi>10.1016/0020-0190(88)90099-3]
• 52: Ravi S. Sandhu , Edward J. Coyne , Hal L. Feinstein , Charles E. Youman, Role-Based Access Control Models, Computer, v.29 n.2, p.38-47, February 1996 [doi>10.1109/2.485845]
• 53: Alfredo De Santis , Anna Lisa Ferrara , Barbara Masucci, Cryptographic key assignment schemes for any access control policy, Information Processing Letters, v.92 n.4, p.199-205, 30 November 2004 [doi>10.1016/j.ipl.2004.03.019]
• 54: Schnyder, W. 1989. Planar graphs and poset dimension. Order 5, 323--343.
• 55: Shen, V. and Chen, T. 2002. A novel key management scheme based on discrete logarithms and polynomial interpolations. Comput. Secur. 21, 2, 164--171.
• 56: Sun, Y. and Liu, K. 2004. Scalable hierarchical access control in secure group communications. In Proceedings of the Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM’04). 1296--1306.
• 57: Mikkel Thorup, On Shortcutting Digraphs, Proceedings of the 18th International Workshop on Graph-Theoretic Concepts in Computer Science, p.205-211, June 19-20, 1992
• 58: Thorup, M. 1995. Shortcutting planar digraphs. Comb. Probab. Comput. 4, 287--315.
• 59: Mikkel Thorup, Parallel shortcutting of rooted trees, Journal of Algorithms, v.23 n.1, p.139-159, April 1997 [doi>10.1006/jagm.1996.0829]
• 60: Trotter, W. 1992. Combinatorics and Partially Ordered Sets: Dimension Theory. Johns Hopkins University Press, Baltimore, MD.
• 61: Tsai, H. and Chang, C. 1995. A cryptographic implementation for dynamic access control in a user hierarchy. Comput. Secur. 14, 2, 159--166.
• 62: W. G. Tzeng, A Time-Bound Cryptographic Key Assignment Scheme for Access Control in a Hierarchy, IEEE Transactions on Knowledge and Data Engineering, v.14 n.1, p.182-188, January 2002 [doi>10.1109/69.979981]
• 63: Jan van Leeuwen , Mark H. Overmars, The Art of Dynamizing, Proceedings on Mathematical Foundations of Computer Science, p.121-131, August 31-September 04, 1981
• 64: Wu, J. and Wei, R. 2004. An access control scheme for partially ordered set hierarchy with provable security. Cryptology ePrint Archive, Report 2004/295. http://eprint.iacr.org/.
• 65: Wu, T. and Chang, C. 2001. Cryptograpic key assignment scheme for hierarchical access control. Int. J. Comput. Syst. Sci. Eng. 1, 1, 25--28.
• 66: Yannakakis, M. 1982. The complexity of the partial order dimension problem. SIAM J. Algebraic Discrete Methods 3, 351--358.
• 67: Andrew C. Yao, Space-time tradeoff for answering range queries (Extended Abstract), Proceedings of the fourteenth annual ACM symposium on Theory of computing, p.128-136, May 05-07, 1982, San Francisco, California, United States [doi>10.1145/800070.802185]
• 68: Yeh, J., Chow, R., and Newman, R. 1998. A key assignment for enforcing access control policy exceptions. In Proceedings of the International Symposium on Internet Technology. 54--59.
• 69: Zhang, Q. and Wang, Y. 2004. A centralized key management scheme for hierarchical access control. In Proceedings of the IEEE Global Telecommunications Conference (GLOBECOM’04). 2067--2071.
• 70: Yuliang Zheng , Thomas Hardjono , Josef Pieprzyk, Sibling Intractable Function Families and Their Applications (Extended Abstract), Proceedings of the International Conference on the Theory and Applications of Cryptology: Advances in Cryptology, p.124-138, November 11-14, 1991
• 71: Zheng, Y., Hardjono, T., and Seberry, J. 1993. New solutions to the problem of access control in a hierarchy. Tech. rep. Department of Computer Science, University of Wollongong.
• 72: Zhong, S. 2002. A practical key management scheme for access control in a user hierarchy. Comput. Secur. 21, 8, 750--759.

INDEX TERMS

Primary Classification:
  K. Computing Milieux
  K.6 MANAGEMENT OF COMPUTING AND INFORMATION SYSTEMS
      K.6.5 Security and Protection (D.4.6, K.4.2)

Additional Classification:
  E. Data
  E.1 DATA STRUCTURES

General Terms:
Algorithms, Design, Security

Keywords:
Efficient key derivation, hierarchical access control, key management