Protecting Location Privacy with Personalized k-Anonymity: Architecture and Algorithms

Abstract

Continued advances in mobile networks and positioning technologies have created a strong market push for location-based applications. Examples include location-aware emergency response, location-based advertisement, and location-based entertainment. An important challenge in wide deployment of location-based services (LBSs) is the privacy-aware management of location information, providing safeguards for location privacy of mobile clients against vulnerabilities for abuse. This paper describes a scalable architecture for protecting location privacy from various privacy threats resulting from uncontrolled usage of LBSs. This architecture includes the development of a personalized location anonymization model and a suite of location perturbation algorithms. A unique characteristic of our location privacy architecture is the use of a flexible privacy personalization framework to support location k-anonymity for a wide range of mobile clients with context-sensitive privacy requirements. This framework enables each mobile client to specify the minimum level of anonymity it desires and the maximum temporal and spatial tolerances it is willing to accept when requesting for k-anonymity preserving LBSs. We devise an efficient message perturbation engine to implement the proposed location privacy framework. The prototype we develop is designed to be run by the anonymity server on a trusted platform and performs location anonymization on LBS request messages of mobile clients, such as identity removal and spatio-temporal cloaking of location information. We study the effectiveness of our location cloaking algorithms under various conditions using realistic location data that is synthetically generated from real road maps and traffic volume data. Our experiments show that the personalized location k-anonymity model together with our location perturbation engine can achieve high resilience to location privacy threats without introducing any significant performance penalty.