Efficient techniques for realizing geo-spatial access control

ABSTRACT

The problem of key management for access control systems has been well-studied, and the literature contains several schemes for hierarchy-based and temporal-based access control. The problem of key management in such systems is how to assign keys to users such that each user is able to compute and have access to the appropriate resources while minimizing computation and storage requirements. In the current paper, we consider key management schemes for geo-spatial access control. That is, the access control policy assigns to a user a specific geographic area, and the user consequently obtains access to her area or information about it.In this work, the geography is modeled as an m × n grid of cells (let m ≥ n). Each cell has its own key associated with it, and a user who wants to access the content of a cell needs to obtain its key. Each user obtains access to a rectangular area (or a finite collection of such rectangles) and is able compute keys corresponding to the cells that comprise her area.Our main result is an efficient scheme with the following properties: (i) each user obtains a small constant number of secret keys that permit access to an arbitrary rectangular sub-grid, (ii) computation to derive the key of a specific cell in that rectangle consists of a constant number of efficient operations, and (iii) the server needs to maintain O(mn(log log m)² log* m) public information accessible to all users. The public storage requirement is the worst-case bound and can be improved if the grid is partitioned into regions where the cells of a region share the same key.

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: Claudio A. Ardagna , Marco Cremonini , Ernesto Damiani , Sabrina De Capitani di Vimercati , Pierangela Samarati, Supporting location-based conditions in access control policies, Proceedings of the 2006 ACM Symposium on Information, computer and communications security, March 21-24, 2006, Taipei, Taiwan [doi>10.1145/1128817.1128850]
• 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: M. Atallah, M. Blanton, and K. Frikken. An efficient and provably-secure time-based key assignment scheme. Under submission, 2006.
• 5: 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]
• 6: 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]
• 7: Vijayalakshmi Atluri , Soon Ae Chun, An Authorization Model for Geospatial Data, IEEE Transactions on Dependable and Secure Computing, v.1 n.4, p.238-254, October 2004 [doi>10.1109/TDSC.2004.32]
• 8: 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
• 9: Elisa Bertino , Barbara Catania , Maria Luisa Damiani , Paolo Perlasca, GEO-RBAC: a spatially aware RBAC, Proceedings of the tenth ACM symposium on Access control models and technologies, June 01-03, 2005, Stockholm, Sweden [doi>10.1145/1063979.1063985]
• 10: 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 (COMPSAC'04), p.396-397, September 28-30, 2004
• 11: 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]
• 12: H. Chien and J. Jan. New hierarchical assignment without public key cryptography. Computers & Security, 22(6):523--526, 2003.
• 13: 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]
• 14: A. De Santis, A. Ferrara, and B. Masucci. Enforcing the security of a time-bound hierarchical key assignment scheme. Information Sciences, 176(12):1684--1694, 2006.
• 15: B. Dushnik and E. Miller. Partially ordered sets. American Journal of Mathematics, 63:600--610, 1941.
• 16: 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]
• 17: H. Hu and D. L. Lee. Energy-efficient monitoring of spatial predicates over moving objects. Bulletin of the IEEE Computer Society Technical Committee on Data Engineering, 28(3):19--26, 2005.
• 18: 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.
• 19: C. Lin. Hierarchical key assignment without public-key cryptography. Computers & Security, 20(7):612--619, 2001.
• 20: Mohamed F. Mokbel , Walid G. Aref , Susanne E. Hambrusch , Sunil Prabhakar, Towards scalable location-aware services: requirements and research issues, Proceedings of the 11th ACM international symposium on Advances in geographic information systems, p.110-117, November 07-08, 2003, New Orleans, Louisiana, USA [doi>10.1145/956676.956691]
• 21: Cynthia A. Patterson , Richard R. Muntz , Cherri M. Pancake, Challenges in Location-Aware Computing, IEEE Pervasive Computing, v.2 n.2, p.80-89, April 2003 [doi>10.1109/MPRV.2003.1203757]
• 22: W. Trotter. Combinatorics and Partially Ordered Sets: Dimension Theory. Johns Hopkins University Press, Baltimore, MD, 1992.
• 23: 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]
• 24: 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]
• 25: Upkar Varshney, Location management for mobile commerce applications in wireless Internet environment, ACM Transactions on Internet Technology (TOIT), v.3 n.3, p.236-255, August 2003 [doi>10.1145/857166.857169]
• 26: 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]
• 27: 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]
• 28: S. Zhong. A practical key management scheme for access control in a user hierarchy. Computers & Security, 21(8):750--759, 2002.

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
      Subjects: Graphs and networks

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

General Terms:
Algorithms, Design, Security

Keywords:
geo-spatial access control, key assignment and derivation, key management