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 the key of a higher class can be used to derive the keys of all classes lower down in the hierarchy, according to temporal constraints.In this paper we design and analyze time-bound hierarchical key assignment schemes which are provably-secure and efficient. We first consider the unconditionally secure setting and we show a tight lower bound on the size of the private information distributed to each class. Then, we consider the computationally secure setting and obtain several results: We first prove that a recently proposed scheme is insecure against collusion attacks. Hence, motivated by the need for provably-secure schemes, we propose two different constructions for time-bound hierarchical key assignment schemes. The first one is based on symmetric encryption schemes, whereas, the second one makes use of bilinear maps. These appear to be the first constructions of time-bound hierarchical key assignment schemes which are simultaneously practical and provably-secure.

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: 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]
• 3: 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]
• 4: G. Ateniese, A. De Santis, A. L. Ferrara, and B. Masucci, Provably-Secure Time-Bound Hierarchical Key Assignment Schemes, IACR ePrint Archive, Report 2006/225.
• 5: Mihir Bellare , Anand Desai , Eron Jokipii , Phillip Rogaway, A Concrete Security Treatment of Symmetric Encryption, Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS '97), p.394, October 19-22, 1997
• 6: Elisa Bertino , Barbara Carminati , Elena Ferrari, A temporal key management scheme for secure broadcasting of XML documents, Proceedings of the 9th ACM conference on Computer and communications security, November 18-22, 2002, Washington, DC, USA [doi>10.1145/586110.586116]
• 7: D. Boneh and X. Boyen, Efficient Selective-ID Secure Identity-based Encryption without Random Oracles, in Proc. of Eurocrypt 2004, LNCS, 3027, 223--238, 2004.
• 8: Dan Boneh , Matthew Franklin, Identity-Based Encryption from the Weil Pairing, SIAM Journal on Computing, v.32 n.3, p.586-615, 2003 [doi>10.1137/S0097539701398521]
• 9: Dan Boneh , Ben Lynn , Hovav Shacham, Short Signatures from the Weil Pairing, Journal of Cryptology, v.17 n.4, p.297-319, September 2004 [doi>10.1007/s00145-004-0314-9]
• 10: R. Canetti, S. Halevi, and J. Katz, A Forward-Secure Public-Key Encryption Scheme, in Proc. of Eurocrypt 2003, LNCS, 2656, 255--271, 2003.
• 11: T. Chen and Y. Chung, Hierarchical Access Control based on Chinese remainder Theorem and Symmetric Algorithm, Comput. & Security, 21(6), 565--570, 2002.
• 12: 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]
• 13: Thomas M. Cover , Joy A. Thomas, Elements of information theory, Wiley-Interscience, New York, NY, 1991
• 14: 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]
• 15: 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.
• 16: Alfredo De Santis , Anna Lisa Ferrara , Barbara Masucci, Unconditionally secure key assignment schemes, Discrete Applied Mathematics, v.154 n.2, p.234-252, 1 February 2006 [doi>10.1016/j.dam.2005.03.025]
• 17: A. De Santis, A. L. Ferrara, and B. Masucci, Efficient Provably-Secure Key Assignment Schemes, manuscript.
• 18: S. D. Galbraith, K. Harrison, and D. Soldera, Implementing the Tate Pairing, in Proc. of the Algorithmic Number Theory Symp., LNCS, 1838, 385--394, 2000.
• 19: Oded Goldreich , Shafi Goldwasser , Silvio Micali, How to construct random functions, Journal of the ACM (JACM), v.33 n.4, p.792-807, Oct. 1986 [doi>10.1145/6490.6503]
• 20: S. Goldwasser and S. Micali, Probabilistic Encryption, Journal of Comput. and Syst. Sci., 28, 270--299, 1984.
• 21: Shafi Goldwasser , Silvio Micali , Ronald L. Rivest, A digital signature scheme secure against adaptive chosen-message attacks, SIAM Journal on Computing, v.17 n.2, p.281-308, April 1988 [doi>10.1137/0217017]
• 22: 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]
• 23: H. F. Huang and C. C. Chang, A New Cryptographic Key Assignment Scheme with Time-Constraint Access Control in a Hierarchy, Comput. Stand. & Int., 26, 159--166, 2004.
• 24: M. S. Hwang, A Cryptographic Key Assignment Scheme in a Hierarchy for Access Control, Math. and Comput. Modeling, 26(1), 27--31, 1997.
• 25: Antoine Joux, A One Round Protocol for Tripartite Diffie-Hellman, Proceedings of the 4th International Symposium on Algorithmic Number Theory, p.385-394, July 02-07, 2000
• 26: Jonathan Katz , Moti Yung, Characterization of Security Notions for Probabilistic Private-Key Encryption, Journal of Cryptology, v.19 n.1, p.67-95, January 2006 [doi>10.1007/s00145-005-0310-8]
• 27: H. T. Liaw, S. J. Wang, and C. L. Lei, A Dynamic Cryptographic Key Assignment Scheme in a Tree Structure, Comput. and Math. with Appl., 25(6), 109--114, 1993.
• 28: C. H. Lin, Dynamic Key Management Schemes for Access Control in a Hierarchy, Comput. Commun., 20, 1381--1385, 1997.
• 29: A. Miyaji, M. Nakabayashi, and S. Takano, New Explicit Conditions for Elliptic Curve Traces for FR-Reduction, IEICE Trans. Fund., E-84(5), 1234--1243, 2001.
• 30: Moni Naor , Omer Reingold, Number-theoretic constructions of efficient pseudo-random functions, Journal of the ACM (JACM), v.51 n.2, p.231-262, March 2004 [doi>10.1145/972639.972643]
• 31: 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]
• 32: Adi Shamir, On the generation of cryptographically strong pseudorandom sequences, ACM Transactions on Computer Systems (TOCS), v.1 n.1, p.38-44, Feb. 1983 [doi>10.1145/357353.357357]
• 33: V. Shen and T. Chen, A Novel Key Management Scheme based on Discrete Logarithms and Polynomial Interpolations, Comput. & Security, 21(2), 164--171, 2002.
• 34: Q. Tang and C. J. Mitchell, Comments on a Cryptographic Key Assignment Scheme, Comput. Standards & Interfaces, 27, 323--326, 2005.
• 35: 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]
• 36: 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]
• 37: 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]
• 38: 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.
• 39: 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]
• 40: T. Wu and C. Chang, Cryptographic Key Assignment Scheme for Hierarchical Access Control, Int. Journal of Comput. Syst. Sci. and Eng., 1(1), 25--28, 2001.

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