The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
최근 위치기반서비스(LBS)의 확산으로 위치 프라이버시에 대한 우려가 높아지고 있다. 지난 수십 년 동안 위치 프라이버시를 보호하기 위한 많은 방법이 제안되었습니다. 특히 GeoI(Geo-Indistinguishability) 기반의 섭동 방식은 차등 프라이버시(Differential Privacy)에서 물려받은 강력한 프라이버시 보장으로 인해 실제 위치를 의사 위치로 무작위로 교란시키는 방식으로 주목받고 있습니다. 그러나 많은 LBS가 도로 네트워크(예: 차량 공유 서비스)를 기반으로 하지만 GeoI는 유클리드 평면을 기반으로 합니다. 이로 인해 불필요한 소음이 발생하여 도로 네트워크의 LBS에 대한 유틸리티와 개인 정보 사이의 균형이 불충분합니다. 이 문제를 해결하기 위해 우리는 더 나은 절충을 달성하기 위해 도로 네트워크의 위치에 대한 새로운 개인 정보 보호 개념인 GeoGI(Geo-Graph-Indistinguishability)를 제안합니다. GeoGI를 만족하는 GEM(Graph-Exponential Mechanism)을 제안한다. 또한 최적화 문제를 공식화하여 트레이드 오프 측면에서 최적의 GEM을 찾습니다. 그러나 최적의 솔루션을 찾기 위한 순진한 방법의 계산 복잡도는 엄청나므로 허용 가능한 시간 내에 근사 솔루션을 찾기 위한 그리디(greedy) 알고리즘을 제안합니다. 마지막으로, 우리의 실험은 우리가 제안한 메커니즘이 절충과 관련하여 최적의 GeoI 메커니즘을 포함한 GeoI 메커니즘보다 성능이 우수함을 보여줍니다.
Shun TAKAGI
Kyoto University
Yang CAO
Kyoto University
Yasuhito ASANO
Toyo University
Masatoshi YOSHIKAWA
Kyoto University
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.
부
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
부
@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},}
부
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 -