A reciprocal framework for spatial K-anonymity

作者:

Highlights:

摘要

Spatial K-anonymity (SKA) exploits the concept of K-anonymity in order to protect the identity of users from location-based attacks. The main idea of SKA is to replace the exact location of a user U with an anonymizing spatial region (ASR) that contains at least K−1 other users, so that an attacker can pinpoint U with probability at most 1/K. Simply generating an ASR that includes K users does not guarantee SKA. Previous work defined the reciprocity property as a sufficient condition for SKA. However, the only existing reciprocal method, Hilbert Cloak, relies on a specialized data structure. In contrast, we propose a general framework for implementing reciprocal algorithms using any existing spatial index on the user locations. We discuss ASR construction methods with different tradeoffs on effectiveness (i.e., ASR size) and efficiency (i.e., construction cost). Then, we present case studies of applying our framework on top of two popular spatial indices (namely, R*-trees and Quad-trees). Finally, we consider the case where the attacker knows the query patterns of each user. The experimental results verify that our methods outperform Hilbert Cloak. Moreover, since we employ general-purpose spatial indices, the proposed system is not limited to anonymization, but supports conventional spatial queries as well.

论文关键词:Location-based services,Anonymity,Privacy,Spatial databases

论文评审过程:Received 22 October 2008, Revised 7 September 2009, Accepted 6 October 2009, Available online 13 October 2009.

论文官网地址:https://doi.org/10.1016/j.is.2009.10.001