Privacy-preserving Navigation Supporting Similar Queries in Vehicular Networks

Abstract

Traffic-sensitive navigation systems in vehicular networks help drivers avoid traffic jams by providing several realtime navigation routes. However, drivers still encounter privacy concerns because their sensitive locations, i.e., their start point and endpoint, are submitted to an honest-but-curious navigation service provider (NSP). Previous privacy-preserving studies exhibit serious deficiencies under similar queries: if a driver makes several similar queries, i.e., periodically makes requests for the same start point and endpoint to the NSP, these requests will eventually reveal the areas of the two points as well as the route. In this paper, we present a novel privacy-preserving navigation scheme PiSim, which supports similar queries in navigation services. Intuitively, we transform the typical navigation approach into a traffic congestion querying approach. Instead of sending two locations to the NSP and awaiting a navigation route, drivers query the traffic congestion along the navigation route. Specifically, PiSim is characterized by extending anonymous authentication, facilitating privacy-preserving multi-keyword fuzzy search, and constructing weighted proximity graphs. Our scheme protects location privacy and route privacy, and defends against multiple requesting, spurious reporting, and collusion attacks from malicious drivers. Finally, a detailed analysis confirms the privacy and security properties of PiSim. Extensive experiments are conducted to demonstrate the feasibility, performance, and privacy protection level.