Measuring Privacy with Distinguishability Metrics: Definitions, Mechanisms and Application to Location Privacy
Mesurer la confidentialité avec des métriques de discernabilité: définitions, mécanismes et confidentialité des informations liées à la localisation
Résumé
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.
La disponibilité croissante de smartphones et tablettes a donné lieu à l’élaboration d’une vaste classe de nouvelles applications, qui recueillent et analysent de grandes quantités d’informations sur leurs utilisateurs pour des raisons différentes: offrir un service personnalisé, offrir de la publicité ciblée, etc. Toutefois, le type et la quantité de données collectées ont engendres des graves préoccupations concernant la vie privée: en effet, ces données sont en général confidentielles par nature, et souvent, elles peuvent être liées à d’autres types d’informations sensibles. Afin de pallier à ces préoccupations, des garanties de confidentialité sont nécessaires. Differential privacy est l’une des notions de confidentialité les plus importantes dans le contexte des bases de données statistiques. Elle fournit une garantie formelle de confidentialité, assurant qu’aucune information sensible concernant des particuliers ne peut être facilement déduite par la divulgation des réponses aux questions globales. Si deux bases de données sont adjacentes, c’est à dire ne diffèrent que pour un individu, la requête ne devrait pas permettre de les distinguer par plus d’un certain facteur. Ceci induit une borne sur la discernabilité qui est déterminée par la distance sur le graphe de Hamming de la relation de contiguïté. Lorsque les informations sensibles à protéger ne sont pas les données relatives à un seul individu, ou lorsque les secrets se sont pas du tout les bases de données, il est courant de considérer les différentes notions de discernabilité, qui dépendent de l’application et de la garantie de confidentialité que nous voulons exprimer.
Dans la première partie de cette thèse, nous explorons les implications de la differential privacy lorsque l’exigence d’indiscernabilité repose sur une notion arbitraire de la distance. Nous pouvons exprimer de cette façon les menaces contre la vie privée qui ne peuvent pas être représentées par la notion standard. Nous donnons des caractérisations intuitives de ces menaces en termes d’adversaires bayésiens. Nous revisitons les résultats connus sur les mécanismes universellement optimaux, et nous montrons que, dans notre contexte, ces mécanismes existent pour les requêtes somme, moyenne, et percentile .
Dans la deuxième partie de cette thèse, nous introduisons le concept de géo-indiscernabilité, une notion formelle de confidentialité pour les systèmes basés sur la localisation. Cette définition est un cas particuliere de la version généralisée de la differential privacy présenté precedemment. Nous présentons aussi un mécanisme qui permet d’atteindre cette notion et nous étudions les différentes questions que pose la mise en œuvre, à savoir la troncature du résultat et l’effet de la précision de la machine. Nous décrivons également comment utiliser notre mécanisme pour améliorer les applications LBS avec des garanties de géo-indiscernabilité sans compromettre la qualité des résultats.
Dans la dernière partie de cette thèse, nous considérons le méchanisme de Shokri et al, qui offre un compromis optimal entre la perte de qualité de service et la protection de la vie privée par rapport à un adversaire bayésien. Nous montrons qu’il est possible de combiner les avantages de cette approche avec la nôtre: étant donné un seuil minimal pour le degré de géo-indiscernabilité, nous construisons un mécanisme qui offre utilité maximale, en resolvant un problème d’optimisation linéaire. Puisque la géo-indiscernabilité est insensible à la reconfiguration d’un adversaire bayésien, ce mécanisme est également optimal dans le sens de Shokri et al. En outre, nous proposons une méthode pour réduire le nombre de contraintes du programme linéaire de cubique è quadratique, élargissant considérablement la taille des ensembles de localisations pour lesquels les mécanismes optimaux peuvent encore être calculés, tout en maintenant les garanties de confidentialité sans affecter significativement l’utilité du mécanisme généré.
Loading...