Privacy and Integrity Preserving Computations with CRISP

In the digital era, users share their personal data with service providers to obtain some utility, e.g., access to high-quality services. Yet, the induced information flows raise privacy and integrity concerns. Consequently, cautious users may want to protect their privacy by minimizing the amount of information they disclose to curious service providers. Service providers are interested in verifying the integrity of the users' data to improve their services and obtain useful knowledge for their business. In this work, we present a generic solution to the trade-off between privacy, integrity, and utility, by achieving authenticity verification of data that has been encrypted for offloading to service providers. Based on lattice-based homomorphic encryption and commitments, as well as zero-knowledge proofs, our construction enables a service provider to process and reuse third-party signed data in a privacy-friendly manner with integrity guarantees. We evaluate our solution on different use cases such as smart-metering, disease susceptibility, and location-based activity tracking, thus showing its versatility. Our solution achieves broad generality, quantum-resistance, and relaxes some assumptions of state-of-the-art solutions without affecting performance.

Quantifying and Protecting Location Privacy

Reza Shokri

Recent developments in information and communication technologies have been profound and life-changing. Most people are now equipped with smart phones with high computation power and communication capabilities. These devices can efficiently run multiple software applications in parallel, store a non-negligible amount of (personal) user data, process various sophisticated sensors and actuators, and communicate over multiple wireless media. Furthermore, they are commonly equipped with high-precision localization capabilities based, for example, on a GPS receiver or on triangulation with nearby base stations or access points. Mobile applications take advantage of this feature to provide location-based services to users. The ever-increasing usage of these personal communication devices and mobile applications, although providing convenience to their owners, comes at a very high cost to their privacy. Interacting with location-based services (LBSs) leaves an almost indelible digital trace of users’ whereabouts. Moreover, the contextual information attached to these traces can reveal users’ personal habits, interests, activities, and relationships. Consequently, exposure of this private information to third parties (such as service providers) escalates their power on individuals, and opens the door to various misuses of users’ personal data. Individuals have the right, and should also have the means to control the amount of their private (location) information that is disclosed to others. In the context of location-based services, various privacy enhancing mechanisms, such as location obfuscation and user anonymization, are proposed in the literature. However, the existing design methodologies for location-privacy preserving mechanisms do not consistently model users’ (privacy and service quality) requirements together with the adversary’s knowledge and objectives. Protection mechanisms are instead designed in an ad hoc manner and irrespective of the adversary model. Consequently, there is a mismatch between the goals and results of these protection mechanisms. Furthermore, the evaluation of privacy preserving mechanisms and their comparison remain problematic because of the absence of a systematic method to quantify them. In particular, the assumptions about the adversary model tend to be incomplete, with the risk of a possibly wrong estimation of the users’ location privacy. Arguably, the lack of a generic analytical framework for specifying protection mechanisms and for evaluating location privacy is evident. The absence of such a framework makes the design of effective protection mechanisms and the objective comparisons between them impossible. In this thesis, we address these issues and provide solutions for a systematic quantification and protection of location privacy. To this end, we construct an analytic framework for location privacy. We formalize users’ mobility model, their access pattern to location-based services, and their privacy and service quality requirements. We also model location-privacy preserving mechanisms as probabilistic functions that obfuscate users’ (location and identity) information before being shared with location-based services. Moreover, in order to quantify users’ location privacy, we propose inference mechanisms that measure users’ information leakage to third parties. They combine various pieces of information about users and estimate (by establishing a probabilistic belief on) users’ private information (e.g., their location at a given time). Therefore, we propose the adversary’s expected estimation error as, arguably, the right metric for location privacy. In our inference framework, we formalize the adversary’s prior knowledge on users, his observation (on the users’ accesses to LBS), and his inference objectives (e.g., re-identifying or localizing users). We assume that adversary constructs a (mobility) profile for each user, to be used in his inference attacks. We make use of statistical tools to construct these profiles, given users’ partial traces. Moreover, we model the inference attacks as the estimation of users’ actual locations, given their profiles and their LBS accesses (observed by the adversary). We mainly use Bayesian inference to perform the estimation. In particular, we use known inference algorithms for hidden Markov models to design de-anonymization, localization, and tracking attacks. To cover more adversary’s objectives, we propose an algorithm for generic location inference attacks, based on Markov-chain Monte-Carlo methods. We also provide a software tool: the Location-Privacy and Mobility Meter (LPM). It is designed based on our formal framework for evaluating the effectiveness of various location-privacy preserving mechanisms and quantifying users’ location privacy. As an example, using LPM, we validate the efficacy of existing location obfuscation and anonymization mechanisms on real location traces. We show that users’ location privacy measured by existing popular metrics, k-anonymity and entropy, is not correlated with the adversary’s success (in learning users’ private information), thus these metrics are inappropriate as privacy metrics. Our results also confirm that anonymization alone is a weak location-privacy preserving mechanism. Moreover, our results show how the resilience of a protection mechanism varies with respect to different inference attacks. Hence, it is a necessity for privacy protection mechanisms to be designed with concrete attack objectives in mind. Relying on these findings, we design optimal location obfuscation techniques tailored against localization attacks. A user needs a protection mechanism that maximizes her location privacy. This is at odds with the objectives of the adversary who designs inference attacks that minimize his estimation error. We propose a game-theoretic methodology that models the conflicting objectives of user and adversary simultaneously. More precisely, we model the problem as a Bayesian Stackelberg game and solve it by using linear programming. In the optimization problem, users constrain the protection mechanism to respect their service quality requirements. This enables us to find the optimal point in the tradeoff curve between privacy and service quality that satisfies both user privacy and service quality requirements. Our results indicate that anticipating for the inference attacks and considering the adversary’s knowledge lead to the design of more effective protection mechanisms. This thesis is a step towards a more systematic modeling, analysis, and design of (location) privacy enhancing technologies. We believe that our analytical approach can be used to quantify and protect privacy in scenarios and domains that are not covered in this thesis.

EPFL2013

Interdependent and Multi-Subject Privacy: Threats, Analysis and Protection

Alexandra-Mihaela Olteanu

In Alan Westin's generally accepted definition of privacy, he describes it as an individual's right 'to control, edit, manage, and delete information about them[selves] and decide when, how, and to what extent information is communicated to others.' Therefore, privacy is an individual and independent human right. The great Mahatma Gandhi once said that 'interdependence is and ought to be as much the ideal of man as selfsufficiency. Man is a social being.' To ensure this independent right to inherently social beings, it will be difficult, if not impossible. This is especially true as today's world is highly interconnected, technology evolves rapidly, data sharing is increasingly abundant, and regulations do not provide sufficient guidance in the realm of interdependency. In this thesis, we explore the topic of interdependent privacy from an adversarial point of view by exposing threats, as well as from an end-user point of view, by exploring awareness, preferences and privacy protection needs. First, we quantify the effect of co-locations on location privacy, considering an adversary such as a social-network operator that has access to this information: Not only can a user be localized due to her reported locations and mobility patterns, but also due to those of her friends (and the friends of her friends and so on). We formalize this problem and propose effective inference algorithms that substantially reduce the complexity of localization attacks that make use of co-locations. Our results show that an adversary can effectively incorporate co-locations in attacks to substantially reduce users' location privacy; this exposes a real and severe threat. Second, we investigate the interplay between the privacy risks and the social benefits of users when sharing (co-)locations on OSNs. We propose a game-theoretic framework for analyzing users' strategic behaviors. We conduct a survey of Facebook users and quantify their benefits of sharing vs. viewing information and their preference for privacy vs. benefits. Our survey exposes deficits in users' awareness of privacy risks in OSNs. Our results further show how users' individual preferences influence, sometimes in a negative way, each other's decisions. Third, we consider various types of interdependent and multi-subject data (photo, colocation, genome, etc.) that often have privacy implications for data subjects other than the uploader, yet can be shared without their consent or awareness. We propose a system for sharing such data in a consensual and privacy-preserving manner. We implement it in the case of photos, by relying on image-processing and cryptographic techniques, as well as on a two-tier architecture. We conduct a survey of Facebook users; it indicates that there is interest in such a system, and that users have increasing privacy concerns due to prejudice or discrimination that they have been or could still easily be exposed to. In conclusion, this thesis provides new insights on users' privacy in the context of interdependence and constitutes a step towards the design of novel privacy-protection mechanisms. It should be seen as a warning message for service providers and regulatory institutions: Unless the interdependent aspects of privacy are considered, this fundamental human right can never be guaranteed.

EPFL2019

Rethinking Location Privacy for Unknown Mobility Behaviors

Carmela González Troncoso, Simón Oya Diez

Location Privacy-Preserving Mechanisms (LPPMs) in the literature largely consider that users' data available for training wholly characterizes their mobility patterns. Thus, they hardwire this information in their designs and evaluate their privacy properties with these same data. In this paper, we aim to understand the impact of this decision on the level of privacy these LPPMs may offer in real life when the users' mobility data may be different from the data used in the design phase. Our results show that, in many cases, training data does not capture users' behavior accurately and, thus, the level of privacy provided by the LPPM is often overestimated. To address this gap between theory and practice, we propose to use blank-slate models for LPPM design. Contrary to the hardwired approach, that assumes known users' behavior, blank-slate models learn the users' behavior from the queries to the service provider. We leverage this blank-slate approach to develop a new family of LPPMs, that we call Profile Estimation-Based LPPMs. Using real data, we empirically show that our proposal outperforms optimal state-of-the-art mechanisms designed on sporadic hardwired models. On non-sporadic location privacy scenarios, our method is only better if the usage of the location privacy service is not continuous. It is our hope that eliminating the need to bootstrap the mechanisms with training data and ensuring that the mechanisms are lightweight and easy to compute help fostering the integration of location privacy protections in deployed systems.