Extended Guess-Answer: Preventing velocity-based linkage attacks in location-based services

When mobile users search points of interest in location based services, they should always provide their accurate locations, which may leak location privacy of themselves. A typical approach to protect user location privacy is to generate a cloaked region (CR) that encloses the user position. However, if locations are continuously reported, an attacker can correlate CRs from multiple timestamps to accurately pinpoint the user position within a CR. In this paper, we present a novel approach, called Extended Guess-Answer, to protect against velocity-based linkage attacks in location based services. Through the interaction between the user and the server, a cloaked region that contains user current location can be generated. The experimental results show that our approach is effective and feasible.