Preventing Restricted Space Inference in Online Route Planning Services

Abstract

Online route planning services compute routes from any given location to a desired destination address. Unlike offline implementations, they do so in a traffic-aware fashion by taking into consideration up-to-date map data and real-time traffic information. In return, users have to provide precise location information about a route’s endpoints to a not necessarily trusted service provider. As suchlike leakage of personal information threatens a user’s privacy and anonymity, this paper presents PrOSPR, a comprehensive approach for using current online route planning services in a privacy-preserving way, and introduces the concept of k-immune route requests to avert inference attacks based on restricted space information. Using a map-based approach for creating cloaked regions for the start and destination addresses, our solution queries the online service for routes between subsets of points from these regions. This, however, might result in the returned path deviating from the optimal route. By means of empirical evaluation on a real road network, we demonstrate the feasibility of our approach regarding quality of service and communication overhead.