Skip to Main content Skip to Navigation
Conference papers

Geo-Graph-Indistinguishability: Protecting Location Privacy for LBS over Road Networks

Abstract : In recent years, Geo-Indistinguishability (GeoI) has been increasingly explored for protecting location privacy in location-based services (LBSs). GeoI is considered a theoretically rigorous location privacy notion since it extends differential privacy to the setting of location privacy. However, GeoI does not consider the road network, which may cause insufficiencies in terms of both privacy and utility for LBSs over a road network. In this paper, we first empirically evaluate the privacy guarantee and the utility loss of GeoI for LBSs over road networks. We identify an extra privacy loss when adversaries have the knowledge of road networks and the degradation of LBS quality of service. Second, we propose a new privacy notion, Geo-Graph-Indistinguishability (GeoGI), for protecting location privacy for LBSs over a road network and design a Graph-Exponential mechanism (GEM) satisfying GeoGI. We also show the relationship between GeoI and GeoGI to explain theoretically why GeoGI is a more suitable privacy notion over road networks. Finally, we evaluate the empirical privacy and utility of the proposed mechanism in real-world road networks. Our experiments confirm that GEM achieves higher utility for LBSs over a road network than the planar Laplace mechanism for GeoI under the same empirical privacy level.
Document type :
Conference papers
Complete list of metadatas

Cited literature [25 references]  Display  Hide  Download
Contributor : Hal Ifip <>
Submitted on : Thursday, November 28, 2019 - 2:25:41 PM
Last modification on : Thursday, November 28, 2019 - 2:29:04 PM
Long-term archiving on: : Saturday, February 29, 2020 - 3:40:56 PM


 Restricted access
To satisfy the distribution rights of the publisher, the document is embargoed until : 2022-01-01

Please log in to resquest access to the document


Distributed under a Creative Commons Attribution 4.0 International License



Shun Takagi, Yang Cao, Yasuhito Asano, Masatoshi Yoshikawa. Geo-Graph-Indistinguishability: Protecting Location Privacy for LBS over Road Networks. 33th IFIP Annual Conference on Data and Applications Security and Privacy (DBSec), Jul 2019, Charleston, SC, United States. pp.143-163, ⟨10.1007/978-3-030-22479-0_8⟩. ⟨hal-02384594⟩



Record views