An official website of the United States government
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.
more »
« less
Enhancing Scalability of Metric Differential Privacy via Secret Dataset Partitioning and Benders Decomposition
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.
more »
« less
- PAR ID:
- 10558221
- Publisher / Repository:
- International Joint Conferences on Artificial Intelligence Organization
- Date Published:
- ISBN:
- 978-1-956792-04-1
- Page Range / eLocation ID:
- 1944 to 1952
- Format(s):
- Medium: X
- Location:
- Jeju, South Korea
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
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.more » « less
-
The rapid growth of GPS technology and mobile devices has led to a massive accumulation of location data, bringing considerable benefits to individuals and society. One of the major usages of such data is travel time prediction, a typical service provided by GPS navigation devices and apps. Meanwhile, the constant collection and analysis of the individual location data also pose unprecedented privacy threats. We leverage the notion of geo-indistinguishability, an extension of differential privacy to the location privacy setting, and propose a procedure for privacy-preserving travel time prediction without collecting actual individual GPS trace data. We propose new concepts to examine the impact of the geo-indistinguishability sanitization on the usefulness of GPS traces and provide analytical and experimental utility analysis for privacy-preserving travel time prediction. We also propose new metrics to measure the adversary error in learning individual GPS traces from the collected sanitized data. Our experiment results suggest that the proposed procedure provides travel time analysis with satisfactory accuracy at reasonably small privacy costs.more » « less
-
Differential privacy concepts have been successfully used to protect anonymity of individuals in population-scale analysis. Sharing of mobile sensor data, especially physiological data, raise different privacy challenges, that of protecting private behaviors that can be revealed from time series of sensor data. Existing privacy mechanisms rely on noise addition and data perturbation. But the accuracy requirement on inferences drawn from physiological data, together with well-established limits within which these data values occur, render traditional privacy mechanisms inapplicable. In this work, we define a new behavioral privacy metric based on differential privacy and propose a novel data substitution mechanism to protect behavioral privacy. We evaluate the efficacy of our scheme using 660 hours of ECG, respiration, and activity data collected from 43 participants and demonstrate that it is possible to retain meaningful utility, in terms of inference accuracy (90%), while simultaneously preserving the privacy of sensitive behaviors.more » « less
-
Abstract Small‐to‐medium businesses are always seeking affordable ways to advertise their products and services securely. With the emergence of mobile technology, it is possible than ever to implement innovative Location‐Based Advertising (LBS) systems using smartphones that preserve the privacy of mobile users. In this paper, we present a prototype implementation of such systems by developing a distributed privacy‐preserving system, which has parts executing on smartphones as a mobile app, as well as a web‐based application hosted on the cloud. The mobile app leverages Google Maps libraries to enhance the user experience in using the app. Mobile users can use the app to commute to their daily destinations while viewing relevant ads such as job openings in their neighborhood, discounts on favorite meals, etc. We developed a client‐server privacy architecture that anonymizes the mobile user trajectories using a bounded perturbation strategy. A multi‐modal sensing approach is proposed for modeling the context switching of the developed LBS system, which we represent as a Finite State Machine model. The multi‐modal sensing approach can reduce the power consumed by mobile devices by automatically detecting sensing mode changes to avoid unnecessary sensing. The developed LBS system is organized into two parts: the business side and the user side. First, the business side allows business owners to create new ads by providing the ad details, Geo‐location, photos, and any other instructions. Second, the user side allows mobile users to navigate through the map to see ads while walking, driving, bicycling, or quietly sitting in their offices. Experimental results are presented to demonstrate the scalability and performance of the mobile side. Our experimental evaluation demonstrates that the mobile app incurs low processing overhead and consequently has a small energy footprint.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- https://doi.org/10.24963/ijcai.2024/215
