Confidentialité différentielle

Un article de Wikipédia, l'encyclopédie libre.
Sauter à la navigation Sauter à la recherche

La confidentialité différentielle[1], 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.

Motivations[modifier | modifier le code]

Généralités[modifier | modifier le code]

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[2].

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

Prix Netflix[modifier | modifier le code]

En 2007, Netflix offrait 1 000 000 $ à quiconque pourrait améliorer de 10% son système de recommandation. 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[4] 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é.

Illustration[modifier | modifier le code]

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[5], 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 quart 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[6],[7].

Formalisation[modifier | modifier le code]

Soit un réel positif et un algorithme probabiliste qui prend pour entrée un jeu de données. Soit l'image de . L'algorithme est dit -différentiellement confidentiel, si, pour tous jeux de données et qui diffèrent d'un seul élément (l'information à propos d'une seule personne) et pour tout sous-ensemble de ,

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 , 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 qui renvoie la somme partielle des 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 et , puis calcule leur différence. Dans cet exemple, et , 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 de en calculant la différence . S'il était amené à recevoir les valeurs via un algorithme -différentiellement confidentiel, pour un suffisamment petit, alors il serait incapable de faire la différence entre et .

Histoire[modifier | modifier le code]

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

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

Notes et références[modifier | modifier le code]

  1. Source pour la traduction en français de Differential Privacy: Benjamin Nguyen, « Techniques d’anonymisation », Statistique et société, vol. 2, no 4,‎ (lire en ligne).
  2. Srivatsava Ranjit Ganta, Shiva Prasad Kasiviswanathan et Adam Smith, « Composition Attacks and Auxiliary Information in Data Privacy », Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, ACM, série KDD '08,‎ , p. 265–273 (ISBN 9781605581934, DOI 10.1145/1401890.1401926, lire en ligne)
  3. Dwork, ICALP 2006.
  4. (en) A. Narayanan et V. Shmatikov, « Robust de-anonymization of large sparse datasets (how to break anonymity of the netflix prize dataset) », Proceedings of IEEE Symposium on Security and Privacy,‎
  5. (en) Cynthia Dwork et Aaron Roth, « The Algorithmic Foundations of Differential Privacy », Foundations and Trends in Theoretical Computer Science,‎
  6. Dwork, Cynthia. "A firm foundation for private data analysis." Communications of the ACM 54.1 (2011): 86-95, supra note 19, page 91.
  7. Bambauer, Jane, Krishnamurty Muralidhar, and Rathindra Sarathy. "Fool's gold: an illustrated critique of differential privacy." Vand. J. Ent. & Tech. L. 16 (2013): 701.
  8. Cynthia Dwork, Frank McSherry, Kobbi Nissim et Adam Smith, « Calibrating Noise to Sensitivity », Private Data Analysis Journal of Privacy and Confidentiality, vol. 7, no 3,‎ , avec une première version à TCC en 2006.
  9. « 2017 Gödel Prize », sur EATCS.
  10. (en) Cynthia Dwork et Aaron Roth, « The Algorithmic Foundations of Differential Privacy », Foundations and Trends® in Theoretical Computer Science, vol. 9, nos 3-4,‎ , p. 211–407 (ISSN 1551-305X et 1551-3068, DOI 10.1561/0400000042, lire en ligne)

Voir aussi[modifier | modifier le code]

Bibliographie[modifier | modifier le code]

Liens externes[modifier | modifier le code]