Spatial Anonymity
Abstract
Let U be a user who is asking via a mobile device (e.g., phone, PDA) a query relevant to his current location, such as ‘‘find the nearest betting office.’’ This query can be answered by a Location Based Service (LBS) in a public web server (e.g., Google Maps, apQuest),which is not trustworthy. Since the query may be sensitive, U uses encryption and a pseudonym, in order to protect his privacy. However, the query still contains the exact location, which may reveal the identity of U. For example, if Uasks the query within his residence, an attacker may use public information (e.g., white pages) to associate the location with U. Spatial k-Anonymity (SKA) solves this problem by ensuring that an attacker cannot identify U as the querying user with probability larger than 1 ∕ k, where k is a user-defined anonymity requirement. To achieve this, a centralized or distributed anonymization service replaces the exact location of U with an area (called Anonymizing Spatial Region or ASR). The ASR encloses U and at least k - 1 additional users. The LBS receives the ASR and retrieves the query results for any point inside the ASR. Those results are forwarded to the anonymization service, which removes the false hits and returns the actual answer to U.
Keywords
Spatial k-anonymity, Privacy-preserving spatial queries, Anonymity in location-based services
Date of this Version
2009
Comments
Encyclopedia of Database Systems 2009, Part 19, 2685-2690