Mesurer la confidentialité avec des métriques de discernabilité: définitions, mécanismes et confidentialité des informations liées à la localisation

Nicolás E. Bordenabe 1, 2
2 COMETE - Concurrency, Mobility and Transactions
LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau], Inria Saclay - Ile de France
Abstract : The increasing availability of smartphone and tablets has given place to the development of a broad new class of applications, which collect and analyze big amounts of information about its users for different reasons: offering a personalized service, offer targeted advertisement, or provide accurate aggregated data for research and analysis purposes. However, serious privacy concerns have been risen about the kind and quantity of data being collected: this data is in general private by nature, and often it can be linked to other kinds of sensitive information. And in most cases, this information is made available to an untrusted entity, either because the service provider itself is not reliable, or because some aggregated information is being publicly released. In order to deal with these concerns, some kind of privacy guarantee is needed. Differential Privacy is one of the most prominent frameworks used to deal with disclosure prevention in statistical databases. It provides a formal privacy guarantee, ensuring that sensitive information relative to individuals cannot be easily inferred by disclosing answers to aggregate queries. If two databases are adjacent, i.e. differ only for an individual, then the query should not allow to tell them apart by more than a certain factor. This induces a bound also on the distinguishability of two generic databases, which is determined by their distance on the Hamming graph of the adjacency relation. When the sensitive information to be protected is other than the value of a single individual, or when the secrets itself are not databases at all, it is common to consider different notions of distinguishability, which depend on the application at hand and the privacy guarantees we wish to express. In the first part of this thesis we explore the implications of differential privacy when the indistinguishability requirement depends on an arbitrary notion of distance. We show that we can naturally express, in this way, (protection against) privacy threats that cannot be represented with the standard notion, leading to new applications of the differential privacy framework. We give intuitive characterizations of these threats in terms of Bayesian adversaries. We revisit the well-known results about universally optimal mechanisms, and show that, in our setting, these mechanisms exist for sum, average, and percentile queries. In the second part of this thesis we introduce geo-indistinguishability, a formal notion of privacy for location-based systems. This privacy definition corresponds to an instance of the generalized version of differential privacy presented before. We also show a mechanism for achieving this notion and study different issues that arise with its implementation, namely the truncation of the result and the effect of the precision of the machine. We also describe how to use our mechanism to enhance LBS applications with geo-indistinguishability guarantees without compromising the quality of the results. In the last part of this thesis, we consider the location privacy framework of Shokri et al., which offers an optimal trade-off between the loss of quality of service and the privacy protection with respect to a given Bayesian adversary. We show that it is possible to combine the advantages of this approach with ours: given a minimum threshold for the degree of geo-indistinguishability, we construct a mechanism that offer maximal utility, as the solution of a linear optimization problem. Since geo-indistinguishability is insensitive to the remapping of a Bayesian adversary, this mechanism is optimal also in the sense of Shokri et al. Furthermore we propose a method to reduce the number of constraints of the linear program from cubic to quadratic, enlarging significantly the size of location sets for which the optimal trade-off mechanisms can still be computed, while maintaining the privacy guarantees without affecting significantly the utility of the generated mechanism.
Document type :
Complete list of metadatas

Cited literature [47 references]  Display  Hide  Download
Contributor : Nicolás E. Bordenabe <>
Submitted on : Monday, December 22, 2014 - 5:33:12 PM
Last modification on : Wednesday, March 27, 2019 - 4:41:28 PM
Long-term archiving on : Monday, March 23, 2015 - 7:45:24 PM


  • HAL Id : tel-01098088, version 1



Nicolás E. Bordenabe. Mesurer la confidentialité avec des métriques de discernabilité: définitions, mécanismes et confidentialité des informations liées à la localisation. Cryptographie et sécurité [cs.CR]. École Polytechnique, 2014. Français. ⟨tel-01098088⟩



Record views


Files downloads