Location Privacy with Road network Mix-zones

Abstract — Mix-zones are recognized as an alternative and complementary approach to spatial cloaking based approach to location privacy protection. Mix-zones break the continuity of location exposure by ensuring that users ’ movements cannot be traced while they reside in a mix-zone. In this paper we provide an overview of various known attacks that make mix-zones on road networks vulnerable and illustrate a set of counter measures to make road network mix-zones attack resilient. Concretely, we categorize the vulnerabilities of road network mix-zones into two classes: one due to the road network characteristics and user mobility, and the other due to the temporal, spatial and semantic correlations of location queries. For instance, the timing information of users ’ entry and exit into a mix-zone provides information to launch a timing attack. The non-uniformity in the transitions taken at the road intersection may lead to transition attack. An example query correlation attack is the basic continual query (CQ) attacks, which attempt to break the anonymity of road network aware mix-zones by performing query correlation based inference. The CQ-timing attacks carry out inference attacks based on both query correlation and timing correlation, and the CQ-transition attacks execute inference attacks based on both query correlation and transition correlation. We study the factors that impact on the effectiveness of each of these attacks and evaluate the efficiency of the counter measures, such as non-rectangle mix-zones and delay tolerant mix-zones, through extensive experiments on traces produced by GTMobiSim at different scales of geographic maps. I