Search for: All records

Geo-obfuscation serves as a location privacy protection mechanism (LPPM), enabling mobile users to share obfuscated locations with servers, rather than their exact locations. This method can protect users’ location privacy when data breaches occur on the server side since the obfuscation process is irreversible. To reduce the utility loss caused by data obfuscation, linear programming (LP) is widely employed, which, however, might suffer from a polynomial explosion of decision variables, rendering it impractical in largescale geo-obfuscation applications. In this paper, we propose a new LPPM, called Locally Relevant Geo-obfuscation (LR-Geo), to optimize geo-obfuscation using LP in a time-efficient manner. This is achieved by confining the geoobfuscation calculation for each user exclusively to the locally relevant (LR) locations to the user’s actual location. Given the potential risk of LR locations disclosing a user’s actual whereabouts, we enable users to compute the LP coefficients locally and upload them only to the server, rather than the LR locations. The server then solves the LP problem based on the received coefficients. Furthermore, we refine the LP framework by incorporating an exponential obfuscation mechanism to guarantee the indistinguishability of obfuscation distribution across multiple users. Based on the constraint structure of the LP formulation, we apply Benders’ decomposition to further enhance computational efficiency. Our theoretical analysis confirms that, despite the geo-obfuscation being calculated independently for each user, it still meets geo-indistinguishability constraints across multiple users with high probability. Finally, the experimental results based on a real-world dataset demonstrate that LR-Geo outperforms existing geo-obfuscation methods in computational time, data utility, and privacy preservation. 

Metric Differential Privacy (mDP) extends the concept of Differential Privacy (DP) to serve as a new paradigm of data perturbation. It is designed to protect secret data represented in general metric space, such as text data encoded as word embeddings or geo-location data on the road network or grid maps. To derive an optimal data perturbation mechanism under mDP, a widely used method is linear programming (LP), which, however, might suffer from a polynomial explosion of decision variables, rendering it impractical in large-scale mDP. In this paper, our objective is to develop a new computation framework to enhance the scalability of the LP-based mDP. Considering the connections established by the mDP constraints among the secret records, we partition the original secret dataset into various subsets. Building upon the partition, we reformulate the LP problem for mDP and solve it via Benders Decomposition, which is composed of two stages: (1) a master program to manage the perturbation calculation across subsets, and (2) a set of subproblems, each managing the perturbation derivation within a subset. Our experimental results on multiple datasets, including geo-location data in the road network/grid maps, text data, and synthetic data, underscore our proposed mechanism’s superior scalability and efficiency. 

Geo-obfuscation is a location privacy protection mechanism used by mobile users to conceal their precise locations when reporting location data, and it has been widely used to protect the location privacy of workers in spatial crowdsourcing (SC). However, this technique introduces inaccuracies in the reported locations, raising the question of how to control the quality loss that results from obfuscation in SC services. Prior studies have addressed this issue in time-insensitive SC settings, where some degree of quality degradation can be accepted and the locations can be expressed with less precision, which, however, is inadequate for time-sensitive SC. In this paper, we aim to minimize the quality loss caused by geo-obfuscation in time-sensitive SC applications. To this end, we model workers’ mobility on a fine-grained location field and constrain each worker’s obfuscation range to a set of peer locations, which have similar traveling costs to the destination as the actual location. We apply a linear programming (LP) framework to minimize the quality loss while satisfying both peer location constraints and geo-indistinguishability, a location privacy criterion extended from differential privacy. By leveraging the constraint features of the formulated LP, we enhance the time efficiency of solving LP through the geo-indistinguishability constraint reduction and the column generation algorithm. Using both simulation and real-world experiments, we demonstrate that our approach can reduce the quality loss of SC applications while protecting workers’ location privacy.