IEICE TRANSACTIONS on Information
Geo-Graph-Indistinguishability: Location Privacy on Road Networks with Differential Privacy
Summary :
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 (GeoI), which randomly perturb a true location to a pseudolocation, are getting attention due to its strong privacy guarantee inherited from differential privacy. However, GeoI 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 (GeoGI), for locations on a road network to achieve a better tradeoff. We propose Graph-Exponential Mechanism (GEM), which satisfies GeoGI. 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 GeoI mechanisms, including optimal GeoI mechanism, with respect to the tradeoff.
- Publication
- IEICE TRANSACTIONS on Information Vol.E106-D No.5 pp.877-894
- Publication Date
- 2023/05/01
- Publicized
- 2023/01/16
- Online ISSN
- 1745-1361
- DOI
- 10.1587/transinf.2022DAP0011
- Type of Manuscript
- Special Section PAPER (Special Section on Data Engineering and Information Management)
- Category
Authors
Shun TAKAGI
Kyoto University
Yang CAO
Kyoto University
Yasuhito ASANO
Toyo University
Masatoshi YOSHIKAWA
Kyoto University
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Shun TAKAGI, Yang CAO, Yasuhito ASANO, Masatoshi YOSHIKAWA, "Geo-Graph-Indistinguishability: Location Privacy on Road Networks with Differential Privacy" in IEICE TRANSACTIONS on Information,
vol. E106-D, no. 5, pp. 877-894, May 2023, doi: 10.1587/transinf.2022DAP0011.
Abstract: 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 (GeoI), which randomly perturb a true location to a pseudolocation, are getting attention due to its strong privacy guarantee inherited from differential privacy. However, GeoI 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 (GeoGI), for locations on a road network to achieve a better tradeoff. We propose Graph-Exponential Mechanism (GEM), which satisfies GeoGI. 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 GeoI mechanisms, including optimal GeoI mechanism, with respect to the tradeoff.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.2022DAP0011/_p
Copy
@ARTICLE{e106-d_5_877,
author={Shun TAKAGI, Yang CAO, Yasuhito ASANO, Masatoshi YOSHIKAWA, },
journal={IEICE TRANSACTIONS on Information},
title={Geo-Graph-Indistinguishability: Location Privacy on Road Networks with Differential Privacy},
year={2023},
volume={E106-D},
number={5},
pages={877-894},
abstract={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 (GeoI), which randomly perturb a true location to a pseudolocation, are getting attention due to its strong privacy guarantee inherited from differential privacy. However, GeoI 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 (GeoGI), for locations on a road network to achieve a better tradeoff. We propose Graph-Exponential Mechanism (GEM), which satisfies GeoGI. 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 GeoI mechanisms, including optimal GeoI mechanism, with respect to the tradeoff.},
keywords={},
doi={10.1587/transinf.2022DAP0011},
ISSN={1745-1361},
month={May},}
Copy
TY - JOUR
TI - Geo-Graph-Indistinguishability: Location Privacy on Road Networks with Differential Privacy
T2 - IEICE TRANSACTIONS on Information
SP - 877
EP - 894
AU - Shun TAKAGI
AU - Yang CAO
AU - Yasuhito ASANO
AU - Masatoshi YOSHIKAWA
PY - 2023
DO - 10.1587/transinf.2022DAP0011
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E106-D
IS - 5
JA - IEICE TRANSACTIONS on Information
Y1 - May 2023
AB - 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 (GeoI), which randomly perturb a true location to a pseudolocation, are getting attention due to its strong privacy guarantee inherited from differential privacy. However, GeoI 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 (GeoGI), for locations on a road network to achieve a better tradeoff. We propose Graph-Exponential Mechanism (GEM), which satisfies GeoGI. 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 GeoI mechanisms, including optimal GeoI mechanism, with respect to the tradeoff.
ER -
English
