New constructions for provably-secure time-bound hierarchical key assignment schemes

ABSTRACT

A time-bound hierarchical key assignment scheme is a method to assign time-dependent encryption keys to a set of classes in a partially ordered hierarchy, in such a way that each class can derive the keys of all classes lower down in the hierarchy, according to temporal constraints.

In this paper we propose new constructions for time-bound hierarchical key assignment schemes which are provably secure with respect to key indistinguishability. Our constructions exhibit a tradeoff among the amount of private information held by each class, the amount of public data, the complexity of key derivation, and the computational assumption on which their security is based.

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: N. Alon and B. Schieber, Optimal Preprocessing for Answering On-line Product Queries, Tech. Rep. TR 71/87, Inst. of Comp. Science, Tel-Aviv Univ., 1987.
• 3: 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]
• 4: Mikhail J. Atallah , Marina Blanton , Keith B. Frikken, Key management for non-tree access hierarchies, Proceedings of the eleventh ACM symposium on Access control models and technologies, June 07-09, 2006, Lake Tahoe, California, USA [doi>10.1145/1133058.1133062]
• 5: Giuseppe Ateniese , Alfredo De Santis , Anna Lisa Ferrara , Barbara Masucci, Provably-secure time-bound hierarchical key assignment schemes, Proceedings of the 13th ACM conference on Computer and communications security, October 30-November 03, 2006, Alexandria, Virginia, USA [doi>10.1145/1180405.1180441]
• 6: 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
• 7: D. Boneh, C. Gentry, and B.Waters, Collusion Resistant Broadcast Encryption with Short Ciphertexts and Private Keys, in Proc. of Crypto 2005, LNCS, 3621, 258--275.
• 8: Hung-Yu Chien, Efficient Time-Bound Hierarchical Key Assignment Scheme, IEEE Transactions on Knowledge and Data Engineering, v.16 n.10, p.1301-1304, October 2004 [doi>10.1109/TKDE.2004.59]
• 9: Jason Crampton , Keith Martin , Peter Wild, On Key Assignment for Hierarchical Access Control, Proceedings of the 19th IEEE workshop on Computer Security Foundations, p.98-111, July 05-07, 2006 [doi>10.1109/CSFW.2006.20]
• 10: A. De Santis, A. L. Ferrara, and B. Masucci, Enforcing the Security of a Time-Bound Hierarchical Key Assignment Scheme, Inf. Sci., 176(12), 1684--1694, 2006.
• 11: A. De Santis, A. L. Ferrara, and B. Masucci, Efficient Provably-Secure Hierarchical Key Assignment Schemes, available as Report 2006/479 at the IACR Cryptology ePrint Archive.
• 12: A. De Santis, A. L. Ferrara, and B. Masucci, New Constructions for Provably-Secure Time-Bound Hierarchical Key Assignment Schemes, available as Report 2006/483 at the IACR Cryptology ePrint Archive.
• 13: B. Dushnik and E. W. Miller, Partially Ordered Sets, American Journal of Mathematics, 63, 600--610, 1941.
• 14: H. F. Huang and C. C. Chang, A New Cryptographic Key Assignment Scheme with Time-Constraint Access Control in a Hierarchy, Comp. Standards & Interfaces 26, 159--166, 2004.
• 15: Q. Tang and C. J. Mitchell, Comments on a Cryptographic Key Assignment Scheme, Comp. Standards & Interfaces, 27, 323--326, 2005.
• 16: Robert Endre Tarjan, Efficiency of a Good But Not Linear Set Union Algorithm, Journal of the ACM (JACM), v.22 n.2, p.215-225, April 1975 [doi>10.1145/321879.321884]
• 17: M. Thorup, Shortcutting Planar Digraphs, DIMACS Tech. Rep. 93-60, August 1993.
• 18: 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]
• 19: Wen-Guey Tzeng, A secure system for data access based on anonymous authentication and time-dependent hierarchical keys, Proceedings of the 2006 ACM Symposium on Information, computer and communications security, March 21-24, 2006, Taipei, Taiwan [doi>10.1145/1128817.1128851]
• 20: 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]
• 21: Jyh-haw Yeh, An RSA-based time-bound hierarchical key assignment scheme for electronic article subscription, Proceedings of the 14th ACM international conference on Information and knowledge management, October 31-November 05, 2005, Bremen, Germany [doi>10.1145/1099554.1099629]
• 22: Xun Yi, Security of Chien's Efficient Time-Bound Hierarchical Key Assignment Scheme, IEEE Transactions on Knowledge and Data Engineering, v.17 n.9, p.1298-1299, September 2005 [doi>10.1109/TKDE.2005.152]
• 23: X. Yi and Y. Ye, Security of Tzeng's Time-Bound Key Assignment Scheme for Access Control in a Hierarchy, IEEE Trans. on Knowl. and Data Eng., 15(4), 1054--1055, 2003.
• 24: Shyh-Yih Wang , Chi-Sung Laih, Merging: An Efficient Solution for a Time-Bound Hierarchical Key Assignment Scheme, IEEE Transactions on Dependable and Secure Computing, v.3 n.1, p.91, January 2006 [doi>10.1109/TDSC.2006.15]

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)

General Terms:
Security

Keywords:
access control, key assignment, provable security