Preventing Multi-query Attack in Location-based Services

Despite increasing popularity, Location-based Services (LBS) (e.g., searching nearby points-of-interest on map) on mobile handheld devices have been subject to major privacy concerns for users. The existing third-party privacy protection methods hide the exact location of users from service providers by sending cloaking regions (CR) that contain several other user locations in the vicinity. However, this has not ensured LBS full immunity from the privacy concerns. In this paper, we describe a serious privacy problem of LBS called multi-query attack. In this attack, the exact location of the service requester can be inferred by the adversary through obtaining cloaking regions that are shrunk or extended in subsequent queries. This problem can be addressed by judiciously retaining, over a period of time, the cloaking regions for the same set of users. Most methods in the literature are weakened for considering only a static snapshot of users during evaluation. Thus, any update due to user movements in real time becomes very costly. Our proposed approach, ANNC (Adaptive Nearest Neighborhood Cloaking),emphasizes developing disjoint sets of users dynamically over time in order to share the common CRs. The CRs are organized in balanced binary trees with restricted height. Thus ANNC achieves the balance between search efficiency and quality of cloaking with higher anonymity levels. The experimental evaluation demonstrates that ANNC will be more efficient in practice than other well-known approaches.