Confidentialité différentielle

La confidentialité différentielle, en bases de données et parfois associé à la cryptographie, est une propriété d'anonymisation pouvant être atteinte via différents mécanismes. Celle-ci vise à définir une forme de protection de résultats de requêtes faites à une de bases de données en minimisant les risques d'identification des entités qu'elle contient, si possible en maximisant la pertinence des résultats de la requête.

Elle permet notamment l'exploitation statistique de données individuelles agrégées, sans compromettre la vie privée des individus.

Motivations

Généralités

La notion d'intimité différentielle est une formalisation du concept intuitif de confidentialité dans le contexte des bases de données statistiques.

Un tiers de confiance dépositaire d'une base de données d'informations sensibles (par exemple dossiers médicaux, registres d'électeurs, métadonnées de courriels) peut souhaiter fournir des informations statistiques, globales sur ces données. Cependant, cela pourrait révéler des informations confidentielles sur les individus. En fait, de nombreuses approches visant à anonymiser des documents publics (telles que le k-anonymat) ont échoué quand les chercheurs ont réussi à identifier les données personnelles en reliant plusieurs bases de données séparément inoffensives.

Elle est parfois présentée comme une « martingale » permettant aux entreprises du numérique d'exploiter les données de leurs utilisateurs, notamment à des fins mercantiles, sans compromettre leur vie privée. Mais, selon Yves-Alexandre de Montjoye (Imperial College, Londres) : « [elle] ne doit pas devenir la solution miracle à tous les problèmes. C'est une belle théorie qui fournit des garanties formelles mais cela reste une technique parmi d'autres dans la boîte à outils de l'"ingénieur en vie privée". À lui ensuite de bien choisir. »

Prix Netflix

De 2006 à 2009, Netflix organisa une compétition offrant 1 000 000 $US à quiconque pourrait améliorer de 10% son système de recommandation (i.e. filtrage collaboratif). La société fournissait un jeu de données permettant aux candidats d'entraîner leurs modèles. Bien que l'entreprise ait au préalable pris soin de remplacer les identifiants clients par des identifiants aléatoires, les chercheurs Arvind Narayanan et Vitaly Shmatikov ont réussi à ré-identifier une partie de ces données à partir des notes attribuées par les membres d'IMDb. En effet, sur IMDb, les membres peuvent noter des films sans que leurs informations personnelles reliées soient anonymisées. C'est à partir de ces informations que les deux chercheurs de l'Université du Texas à Austin ont pu ré-identifier partiellement la base de données fournie par Netflix, révélant de fait l'identité et les attributs de clients de la société. Pour ces raisons, la deuxième édition en 2010 n'a pas été reconduite.

Illustration

La confidentialité différentielle est souvent obtenue en appliquant un procédé qui introduit de l'aléa dans les données. Un exemple simple, qui s'est notamment développé en sciences sociales, est de demander à une personne de répondre à la question "Possédez-vous l'attribut A ?" selon le déroulement suivant :

1. Lancer une pièce.
2. Si pile, alors répondre honnêtement.
3. Si face, alors lancer à nouveau la pièce et répondre "Oui" si face, "Non" si pile.

La confidentialité surgit du caractère réfutable de chacune des réponses individuelles. En particulier, si A est synonyme de comportement illégal, alors répondre "Oui" n'est pas incriminant, dans la mesure où la personne a une probabilité d'un quart de réponse "Oui", quel qu'il en soit. Mais, de façon globale, ces données sont significatives, puisque les réponses positives sont données à un quart par des personnes qui n'ont pas l'attribut A et à trois quarts par des personnes qui le possèdent véritablement. Ainsi, si p est la proportion véritable de personnes ayant A, alors on s'attend à obtenir (1/4)(1-p) + (3/4)p = (1/4) + p/2 réponses positives. D'où une estimation possible de p.

Bien que cette illustration, s'inspirant de la réponse aléatoire, puisse s'appliquer à la divulgation de micro-données (c'est-à-dire de jeu de données contenant une entrée par participant), la confidentialité différentielle exclut par définition ce type de divulgation, en ne permettant que la divulgation de données agrégées par requêtes. En effet, la divulgation de micro-données violerait les axiomes fondant la confidentialité différentielle, dont notamment le déni plausible d'inclusion ou d'exclusion de participants.

Formalisation

Soit $\varepsilon$ un réel positif et ${\mathcal {A}}$ un algorithme probabiliste qui prend pour entrée un jeu de données. Soit ${\textrm {im}}{\mathcal {A}}$ l'image de ${\mathcal {A}}$. L'algorithme ${\mathcal {A}}$ est dit $\varepsilon$-différentiellement confidentiel, si, pour tous jeux de données $D_{1}$ et $D_{2}$ qui diffèrent d'un seul élément (l'information à propos d'une seule personne) et pour tout sous-ensemble $S$ de ${\textrm {im}}{\mathcal {A}}$,

$\Pr[{\mathcal {A}}(D_{1})\in S]\leq e^{\varepsilon }\times \Pr[{\mathcal {A}}(D_{2})\in S],$

où la probabilité est fondée sur l'aléa introduit par l'algorithme.

D'après cette définition, la confidentialité différentielle porte sur l'algorithme lui-même, et non sur les données traitées. Intuitivement, cela signifie que pour deux jeux de données voisins, un algorithme différentiellement confidentiel se comportera à peu près de la même façon sur les deux bases. La définition donne une solide garantie que la présence ou l'absence d'un individu dans la base n'affectera pas significativement la sortie finale de l'algorithme.

Par exemple, supposons que nous détenions une base de données médicales $D_{1}$, dans laquelle chaque enregistrement contient deux informations (Nom, X), où X est un booléen indiquant si la personne a le diabète ou non. Par exemple :

Nom	A le diabète (X)
Vincent	1
Agathe	1
Martin	0
Hélène	0
Sophie	1

Maintenant, supposons qu'un utilisateur malintentionné veuille savoir si Sophie a le diabète ou non. Supposons également qu'il connaisse quelle ligne lui corresponde. Cet utilisateur est uniquement autorisé à demander les données à travers une formulaire de demande $F_{i}$ qui renvoie la somme partielle des $i$ premières lignes de la colonne X de la base de données. Afin de connaître l'état de santé de Sophie, l'utilisateur demande $F_{5}(D_{1})$ et $F_{4}(D_{1})$, puis calcule leur différence. Dans cet exemple, $F_{5}(D_{1})=3$ et $F_{4}(D_{1})=2$, soit une différence de 1. Cette dernière nous indique donc que la valeur attribuée à Sophie est de 1. Cet exemple souligne la façon dont les informations individuelles peuvent être décelées, sans forcément demander de données individuelles.

En poursuivant avec cet exemple, si l'on construit maintenant une base D2 en remplaçant (Sophie, 1) par (Sophie, 0), alors cet utilisateur sera capable de distinguer $D_{2}$ de $D_{1}$ en calculant la différence $F_{5}-F_{4}$. S'il était amené à recevoir les valeurs $F_{i}$ via un algorithme $\varepsilon$-différentiellement confidentiel, pour un $\varepsilon$ suffisamment petit, alors il serait incapable de faire la différence entre $D_{2}$ et $D_{1}$.

Histoire

Un article fondateur du domaine est Calibrating Noise to Sensitivity, publié en 2006. Il a valu à ses auteurs, Cynthia Dwork, Frank McSherry, Kobbi Nissim et Adam Smith, le prix Gödel 2017.

Un article présentant une vue d'ensemble du domaine, The Algorithmic Foundation of Differential Privacy, publié en 2014, sert également de référence dans le domaine.

Le 5 septembre 2019, l'entreprise Google publie sur GitHub le code d'une bibliothèque logicielle de confidentialité différentielle employable dans des logiciels tiers. Ses auteurs présentent ce code comme celui que Google utilise en interne. Il n'utiliserait pas d'algorithmes très sophistiqués, mais aurait le mérite d'être robuste, complet, facile à implémenter, et devrait être maintenu dans le temps.

Voir aussi

Bibliographie

• The Algorithmic Foundations of Differential Privacy by Cynthia Dwork and Aaron Roth. Foundations and Trends in Theoretical Computer Science. Vol. 9, no. 3–4, pp. 211‐407, Aug. 2014. DOI=10.1561/0400000042
• Calibrating Noise to Sensitivity in Private Data Analysis by Cynthia Dwork, Frank McSherry, Kobbi Nissim, Adam Smith In Theory of Cryptography Conference (TCC), Springer, 2006.
• Differential Privacy by Cynthia Dwork, International Colloquium on Automata, Languages and Programming (ICALP) 2006, p. 1–12.
• Frank D. McSherry. 2009. Privacy integrated queries: an extensible platform for privacy-preserving data analysis. In Proceedings of the 35th SIGMOD international conference on Management of data (SIGMOD '09), Carsten Binnig and Benoit Dageville (Eds.). ACM, New York, NY, États-Unis, 19-30. DOI= 10.1145/1559845.1559850

Liens externes

• The Algorithmic Foundations of Differential Privacy by Cynthia Dwork and Aaron Roth, 2014.
• Differential Privacy: A Survey of Results by Cynthia Dwork, Microsoft Research April 2008
• Privacy of Dynamic Data: Continual Observation and Pan Privacy by Moni Naor, Institute for Advanced Study November 2009
• Tutorial on Differential Privacy by Katrina Ligett, California Institute of Technology, December 2013
• A Practical Beginner's Guide To Differential Privacy by Christine Task, Purdue University April 2012
• Private Map Maker v0.2 on the Common Data Project blog