POSTER: Protecting Location Privacy on Road Networks

Our recent proposed notion Geo-Graph-Indistinguishability (GeoGI) is a theoretically rigorous location privacy notion which extends differential privacy to the setting of location privacy on a road network modeled by a graph. GeoGI is practically more useful for protecting location privacy in location-based services (LBSs) such as UBER than a previously proposed Geo-Indistinguishability (Geo-I), which is a popular notion of location privacy defined on the Euclidean plane. We also proposed a Graph-Exponential Mechanism (GEM) based on GeoGI. In this paper, we analyze the utility and privacy of GEM. This analysis makes following two contributions to build a user-friendly location perturbation system. First, our proposed system makes a privacy parameter easy to interpret. The privacy parameter of GEM is not interpretable for ordinary people. By converting to the interpretable value, a user can choose his/her preferred privacy level and utility. Second, we formalize an optimization problem to find the optimal range of GEM according to an arbitrary LBS w.r.t the utility-privacy trade-off for a certain user. Experimental results with real-world data show that our optimization improves the utility-privacy trade-off.