2020/10/26 by Shun Takagi, Takagi, Shun, Yang Cao +5
Computer Science · Engineering · #Cryptography and Security (cs.CR) #FOS: Computer and information sciences #Mobile Crowdsensing and Crowdsourcing #Privacy-Preserving Technologies in Data #Vehicular Ad Hoc Networks (VANETs) #cs.CR
paper · pdf · doi:10.48550/arxiv.2010.13449
arxiv created 2020/10/26 · openalex publication_date 2020/10/26 · arxiv updated 2020/10/27 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In recent years, concerns about location privacy are increasing with the spread of location-based services (LBSs). Many methods to protect location privacy have been proposed in the past decades. Especially, perturbation methods based on Geo-Indistinguishability (Geo-I), which randomly perturb a true location to a pseudolocation, are getting attention due to its strong privacy guarantee inherited from differential privacy. However, Geo-I is based on the Euclidean plane even though many LBSs are based on road networks (e.g. ride-sharing services). This causes unnecessary noise and thus an insufficient tradeoff between utility and privacy for LBSs on road networks. To address this issue, we propose a new privacy notion, Geo-Graph-Indistinguishability (GG-I), for locations on a road network to achieve a better tradeoff. We propose Graph-Exponential Mechanism (GEM), which satisfies GG-I. Moreover, we formalize the optimization problem to find the optimal GEM in terms of the tradeoff. However, the computational complexity of a naive method to find the optimal solution is prohibitive, so we propose a greedy algorithm to find an approximate solution in an acceptable amount of time. Finally, our experiments show that our proposed mechanism outperforms a Geo-I's mechanism with respect to the tradeoff.