GIT-CERCS-04-15
Bugra Gedik, Ling Liu,
A Customizable k-Anonymity Model for Protecting Location Privacy
Continued advances in mobile networks and positioning
technologies have created a strong market push
for location-based services (LBSs). Examples include
location-aware emergency services, location based service
advertisement, and location sensitive billing. One of
the big challenges in wide deployment of LBS systems
is the privacy-preserving management of location-based
data. Without safeguards, extensive deployment of location
based services endangers location privacy of mobile
users and exhibits significant vulnerabilities for abuse.
In this paper, we describe a customizable k-anonymity
model for protecting privacy of location data. Our model
has two unique features. First, we provide a customizable
framework to support k-anonymity with variable k,
allowing a wide range of users to benefit from the location
privacy protection with personalized privacy requirements.
Second, we design and develop a novel spatio-temporal
cloaking algorithm, called CliqueCloak, which provides
location k-anonymity for mobile users of a LBS provider.
The cloaking algorithm is run by the location protection
broker on a trusted server, which anonymizes messages
from the mobile nodes by cloaking the location information
contained in the messages to reduce or avoid privacy
threats before forwarding them to the LBS provider(s).
Our model enables each message sent from a mobile node
to specify the desired level of anonymity as well as the
maximum temporal and spatial tolerances for maintaining
the required anonymity. We study the effectiveness of the
cloaking algorithm under various conditions using realistic
location data synthetically generated using real road maps
and traffic volume data. Our experiments show that the
location k-anonymity model with multi-dimensional cloaking
and tunable k parameter can achieve high guarantee of
k anonymity and high resilience to location privacy threats
without significant performance penalty.