Confidentialité différentielle

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

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

${\displaystyle \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 ${\displaystyle 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 :

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 ${\displaystyle F_{i}}$ qui renvoie la somme partielle des ${\displaystyle 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 ${\displaystyle F_{5}(D_{1})}$ et ${\displaystyle F_{4}(D_{1})}$, puis calcule leur différence. Dans cet exemple, ${\displaystyle F_{5}(D_{1})=3}$ et ${\displaystyle 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 ${\displaystyle D_{2}}$ de ${\displaystyle D_{1}}$ en calculant la différence ${\displaystyle F_{5}-F_{4}}$. S'il était amené à recevoir les valeurs ${\displaystyle F_{i}}$ via un algorithme ${\displaystyle \varepsilon }$-différentiellement confidentiel, pour un ${\displaystyle \varepsilon }$ suffisamment petit, alors il serait incapable de faire la différence entre ${\displaystyle D_{2}}$ et ${\displaystyle D_{1}}$.

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

Un article présentant une vue d'ensemble du domaine, The Algorithmic Foundation of Differential Privacy[11], 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[12] - [2]. 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[13], et devrait être maintenu dans le temps[14].