Efficient techniques for realizing geo-spatial access control

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.