La confidentialité différentielle est passée des articles de recherche aux gros titres de l’actualité technologique l’année dernière lorsque, lors du keynote de la WWDC, Craig Federighi, vice-président de l’ingénierie d’Apple, a annoncé l’utilisation du concept par Apple pour protéger la confidentialité des utilisateurs dans iOS.

C’était le dernier exemple d’une tendance générale : les utilisateurs et les ingénieurs s’éveillaient à l’importance de la protection de la vie privée dans les logiciels. Des violations de la vie privée très médiatisées telles que le « mode divin » d’Uber ont démontré en termes frappants la facilité avec laquelle les employés d’une entreprise peuvent utiliser à mauvais escient les données sensibles recueillies auprès de leurs clients.

La quantité de données sensibles enregistrées numériquement augmente rapidement. Les gens comptent plus que jamais sur les services numériques pour leurs paiements, leurs transports, leur navigation, leurs achats et leur santé. Cette nouvelle collecte de données crée de plus en plus de façons de violer la vie privée.

Mais cela crée également des opportunités intéressantes — améliorer les réseaux de transport, réduire la criminalité, guérir les maladies — si elles sont mises à la disposition des scientifiques et des chercheurs de données appropriés. Il existe une tension naturelle entre la protection de la vie privée des individus dans l’ensemble de données et l’activation d’analyses qui pourraient conduire à un monde meilleur.

Les algorithmes différentiellement privés sont une solution technique prometteuse qui pourrait atténuer cette tension, permettant aux analystes d’effectuer une analyse agrégée bénigne tout en garantissant une protection significative de la vie privée de chaque individu.

Ce domaine technologique en développement mérite d’être pris en compte dans tout système qui cherche à analyser des données sensibles. Bien que la garantie différentielle de la vie privée ait été conçue il y a seulement dix ans, elle a été couronnée de succès dans le milieu universitaire et l’industrie. Les chercheurs inventent et améliorent rapidement des algorithmes différentiellement privés, dont certains ont été adoptés dans iOS d’Apple et Chrome de Google.

Cet article traite des facteurs historiques conduisant à la confidentialité différentielle dans sa forme actuelle, ainsi que d’une définition de la confidentialité différentielle et d’exemples d’algorithmes différentiellement privés. Il examine ensuite certaines implémentations récentes de haut niveau d’algorithmes différentiellement privés par Google, Apple et d’autres.

Contexte

Les algorithmes différentiellement privés sont les derniers d’un domaine vieux de plusieurs décennies de technologies pour l’analyse de données préservant la confidentialité. Deux concepts antérieurs ont directement influencé la confidentialité différentielle :

1. Taille minimale de l’ensemble de requêtes
2. La définition de divulgation statistique de Dalenius.

Nous allons d’abord les expliquer car ils fournissent un contexte utile pour la confidentialité différentielle.

Taille minimale de l’ensemble de requêtes Le premier concept est une taille minimale de l’ensemble de requêtes, qui — comme les algorithmes différentiellement privés — vise à assurer la sécurité des requêtes agrégées. Les requêtes agrégées sont celles dans lesquelles la valeur renvoyée est calculée sur un sous-ensemble d’enregistrements de l’ensemble de données, tels que les dénombrements, les moyennes ou les sommes. Il peut être utile de considérer les requêtes agrégées comme des requêtes SQL commençant par « SELECT SUM », « SELECT COUNT » ou « SELECT AVG « . Les autres types de requêtes agrégées comprennent les tableaux de contingence et les histogrammes.

Une taille d’ensemble de requêtes minimale est une contrainte qui vise à garantir que les requêtes agrégées ne peuvent pas divulguer d’informations sur les individus. Étant donné un certain nombre de seuil configuré T, il garantit que chaque requête agrégée est effectuée sur un ensemble d’au moins T enregistrements. Une taille de jeu de requêtes minimale bloquerait les requêtes agrégées ciblant moins de T individus. Par exemple, si T = 2, il bloquerait ce qui suit :

« SÉLECTIONNEZ AVG (salaire) OÙ name = ‘Troy Brown’; ».

parce que cette requête effectuerait une moyenne sur un enregistrement (nous supposons qu’il n’y a qu’un seul Troy Brown).

L’utilisation de tailles de jeu de requêtes minimales empêche certaines attaques, mais n’est pas assortie d’une garantie de confidentialité et, en pratique, peut être contournée par des attaquants qualifiés. Par exemple, l’attaquant pourrait accomplir l’attaque ci-dessus avec :

« SELECT SUM(salary); ».

« SÉLECTIONNEZ SOMME (salaire) OÙ nom!= ‘Troy Brown’; ».

Ou même, si nous connaissons l’âge de Troy Brown (45 ans) et la position (WR) l’identifient de manière unique:

« SÉLECTIONNEZ SUM (salary) OÙ position=’WR’; ».

« SÉLECTIONNEZ SUM (salaire) OÙ position =’WR’ ET âge!= 45;

De telles attaques sont appelées attaques de suivi, et elles ne peuvent pas être arrêtées par une contrainte de taille de jeu de requêtes minimale. En raison de ces attaques, la taille minimale des ensembles de requêtes a été jugée insuffisante pour protéger les systèmes de requêtes (voir les travaux de Denning). Quelque chose de mieux, avec une garantie, était nécessaire pour garantir la confidentialité.

Définition de la divulgation statistique de Dalenius

En 1977, le statisticien Tore Dalenius a proposé une définition stricte de la confidentialité des données: que l’attaquant ne devrait rien apprendre sur un individu qu’il ne connaissait pas avant d’utiliser l’ensemble de données sensibles. Bien que cette garantie ait échoué (et nous verrons pourquoi), il est important de comprendre pourquoi la confidentialité différentielle est construite telle quelle.

La définition de Dalenius a échoué car, en 2006, l’informaticienne Cynthia Dwork a prouvé que cette garantie était impossible à donner — en d’autres termes, tout accès à des données sensibles violerait cette définition de la vie privée. Le problème qu’elle a constaté était que certains types de renseignements généraux pouvaient toujours mener à une nouvelle conclusion au sujet d’une personne. Sa preuve est illustrée dans l’anecdote suivante: Je sais qu’Alice mesure deux pouces de plus que la moyenne des femmes lituaniennes. Ensuite, j’interagis avec un ensemble de données de femmes lituaniennes et calcule la taille moyenne, que je ne connaissais pas auparavant. Je connais maintenant exactement la taille d’Alice, même si elle n’était pas dans le jeu de données. Il est impossible de tenir compte de tous les types d’informations de base qui pourraient conduire à une nouvelle conclusion sur un individu à partir de l’utilisation d’un ensemble de données.

Dwork, après avoir prouvé ce qui précède, a proposé une nouvelle définition: confidentialité différentielle.

Qu’est-ce que la confidentialité différentielle ?

La confidentialité différentielle garantit ce qui suit: que l’attaquant ne peut pratiquement rien apprendre de plus sur un individu que s’il n’avait pas d’enregistrement de cette personne dans l’ensemble de données. Bien que plus faible que la définition de la vie privée de Dalenius, la garantie est suffisamment forte car elle s’aligne sur les incitations du monde réel — les individus n’ont aucune incitation à ne pas participer à un ensemble de données, car les analystes de cet ensemble de données tireront les mêmes conclusions sur cet individu, que l’individu s’inclut ou non dans l’ensemble de données. Comme leurs informations personnelles sensibles ne sont presque pas pertinentes dans les sorties du système, les utilisateurs peuvent être assurés que l’organisation qui gère leurs données ne viole pas leur vie privée.

Les analystes qui n’apprennent « pratiquement rien de plus sur un individu » signifient qu’ils sont limités à un changement insignifiant de croyance à l’égard d’un individu. (Ici et ci-dessous, « changement » fait référence au changement entre l’utilisation d’un ensemble de données et l’utilisation du même ensemble de données moins l’enregistrement d’une personne.) L’étendue de ce changement est contrôlée par un paramètre appelé ϵ, qui définit la limite sur le changement de probabilité de tout résultat. Une faible valeur de ϵ, telle que 0,1, signifie que très peu de choses peuvent changer dans les croyances d’un individu. Une valeur élevée de ϵ, comme 50, signifie que les croyances peuvent changer beaucoup plus. La définition formelle est la suivante.

Un algorithme A estdiffer- différentiellement privé si et seulement si :

Pr ≤ e ^ **Pr

pour tous les x et pour toutes les paires d’ensembles de données D, D ‘ où D ‘ est D avec un enregistrement quelconque — c’est-à-dire les données d’une personne – manquantes. Le symbole e fait référence à la constante mathématique. Notez que cette définition n’a de sens que pour les algorithmes randomisés. Un algorithme qui donne une sortie déterministe n’est pas un candidat à la confidentialité différentielle.

Le principal attrait de la garantie de confidentialité différentielle est sa limitation du montant que tout analyste peut apprendre sur une personne. De plus, il possède les propriétés utiles suivantes:

• Composabilité: si deux requêtes sont répondues avec des garanties de confidentialité différentielles de niveau ϵ1 et ϵ2, la paire de requêtes est couverte par une garantie de niveau (ϵ1 + ϵ2). Rappelons qu’une valeur plus élevée de ϵ signifie une garantie plus faible.
• Force contre des informations de fond arbitraires: la garantie ne repose en aucune façon sur les informations de fond que l’attaquant connaît. Cette propriété est l’une des principales raisons pour lesquelles la confidentialité différentielle est plus forte qu’une garantie de confidentialité antérieure, k-anonymity.
• Sécurité en post-traitement: il n’y a aucune restriction sur ce qui peut être fait avec un résultat différentiellement privé – peu importe ce avec quoi il est combiné ou comment il est transformé, il est toujours différentiellement privé.

Comment cette garantie est-elle obtenue dans le logiciel ? Les algorithmes différentiellement privés sont des algorithmes randomisés qui ajoutent du bruit à des points clés de l’algorithme. L’un des algorithmes les plus simples est le mécanisme de Laplace, qui peut post-traiter les résultats des requêtes agrégées (par exemple, les nombres, les sommes et les moyennes) pour les rendre différentiellement privés. Voici un exemple de code Java pour le mécanisme Laplace spécifique aux requêtes count:

import org.apache.commons.math3.distribution.LaplaceDistribution;double laplaceMechanismCount(long realCountResult, double epsilon) { LaplaceDistribution ld = new LaplaceDistribution(0, 1 / epsilon); double noise = ld.sample(); return realCountResult + noise;}

Les éléments clés de cette fonction sont

1. Instanciez une distribution de probabilité de Laplace (voir Figure 1) centrée sur 0 et mise à l’échelle de 1/ϵ. Nous utilisons l’implémentation Apache Commons, « LaplaceDistribution », qui est construite avec deux arguments : la moyenne de la distribution et l’échelle de la distribution. Notez qu’un epsilon inférieur (plus d’intimité) entraîne une plus grande échelle et donc une distribution plus large et plus de bruit.
2. Prélevez un échantillon aléatoire de cette distribution. Cette fonction sample() prend un nombre aléatoire compris entre 0 et 1 et applique la fonction de distribution cumulative inverse (CDF) de la distribution de Laplace à ce nombre. Ce processus aboutit à un nombre aléatoire tel que sa probabilité d’être une valeur spécifique corresponde à la distribution. Comme autre façon d’y penser, si cette fonction d’échantillon était invoquée un million de fois pour obtenir un million d’échantillons, la forme de l’histogramme de ces échantillons correspondrait étroitement à la forme de la distribution de Laplace.
3. Perturbe la valeur réelle en ajoutant la valeur aléatoire de l’étape 2.

Considérons pourquoi cet algorithme est différentiellement privé en prenant le point de vue d’un attaquant nommé Eve. Disons que l’ensemble de données est des données de santé mentale, et Eve a conçu une attaque de suivi (voir ci-dessus) qui révélera si sa cible, Bob, reçoit des conseils pour l’alcoolisme ou non. Si le résultat de la requête est 48, Eve sait que Bob reçoit des conseils; si c’est 47, Eve sait le contraire.

Que la réponse soit 47 ou 48, le mécanisme de Laplace renverra un résultat bruyant quelque part autour de 47 ou 48. Il peut renvoyer 49, 46, voire, avec une probabilité plus faible, 44 ou 51 (voir la figure 2 pour un histogramme). En pratique, il est impossible pour Eve d’être très sûre de savoir si la vraie réponse était 47 ou 48 et, par conséquent, ses croyances quant à savoir si Bob est en consultation pour alcoolisme ou maintenant ne changeront pas de manière significative.

Figure 1: La distribution de Laplace centrée à 0 avec une échelle de 1. Sur la photo est la fonction de densité de probabilité (PDF) de la distribution — l’axe des ordonnées est la probabilité relative que la variable prenne la valeur sur l’axe des abscisses.

Figure 2: Les résultats probables de la requête de comptage pour les deux scénarios, où la réponse réelle est 47 et quand elle est 48. Un petit nombre de produits ne suffirait pas à distinguer de quelle distribution ils proviennent. Epsilon est réglé sur 0,67.

Vous avez peut-être observé à ce stade qu’Eve pouvait couper le bruit en répétant la requête plusieurs fois et en voyant si les réponses se regroupaient autour de 47 ou 48. Pour éviter cette tactique, les systèmes différentiellement privés doivent avoir un « budget de confidentialité », un plafond sur la somme des ϵ utilisés dans chaque requête. Ce plafond fonctionne en raison de la propriété de composabilité de la confidentialité différentielle décrite ci-dessus. Ils peuvent poser quelques requêtes à bruit relativement faible, ou plusieurs centaines de requêtes à bruit élevé, mais de toute façon, ils ne seront pas en mesure d’établir en toute confiance si la vraie réponse est 47 ou 48.

Enfin, notez que le mécanisme de Laplace pour les comptages n’est qu’un simple algorithme différentiellement privé. Le mécanisme de Laplace peut être étendu pour fonctionner pour les sommes et autres requêtes agrégées. En outre, il existe des algorithmes fondamentalement différents qui ont été prouvés pour satisfaire la garantie de confidentialité différentielle. Quelques-uns méritent d’être explorés sont l’algorithme des Poids Multiplicatifs Privés, le Mécanisme Exponentiel des Poids Multiplicatifs et la DualQuery.

Confidentialité différentielle en action

En juin 2016, Apple a annoncé qu’il commencerait à utiliser des algorithmes différentiellement privés pour collecter des statistiques comportementales à partir d’iPhones. Cette annonce, en plus de provoquer un énorme pic d’intérêt différentiel pour la protection de la vie privée, a montré que la protection différentielle peut aider les grandes organisations à tirer une nouvelle valeur de données qu’elles ne touchaient pas auparavant en raison de problèmes de confidentialité.

Bien qu’Apple ait jusqu’à présent rendu peu de détails publics, l’algorithme utilisé dans l’iPhone semble similaire au projet RAPPOR de Google. Google a implémenté une fonctionnalité dans Chrome qui collecte des statistiques comportementales à partir des navigateurs Chrome via un algorithme de réponse randomisée différentiellement privé.

Dans la réponse randomisée, le bruit aléatoire est ajouté aux statistiques avant qu’elles ne soient soumises au collecteur. Par exemple, si la statistique réelle est 0, le navigateur remplacera avec une certaine probabilité 0 par un 0 ou 1 sélectionné au hasard. Chaque utilisateur a un degré élevé de négation de la valeur rapportée par son logiciel, car il pourrait s’agir d’une valeur aléatoire. Mais collectivement, le signal se démarque du bruit aléatoire et l’organisation qui collecte les statistiques (c’est-à-dire Google ou Apple) peut observer avec précision les tendances.

Fait intéressant, ni Google ni Apple, à notre connaissance, n’ont révélé la valeur de ϵ qui va avec leur garantie de confidentialité différentielle. Nous avons besoin de cette valeur pour comprendre la protection offerte par la garantie. S’ils utilisent une valeur suffisamment élevée de ϵ, les analystes peuvent toujours apprendre des faits sensibles sur les utilisateurs avec une grande confiance. Une faible valeur de ϵ est requise pour une protection significative de la vie privée.

Des algorithmes différentiellement privés ont également été implémentés dans des produits d’analyse préservant la confidentialité, tels que ceux développés par mon employeur Privitar. Ces produits permettent aux entreprises qui travaillent avec des données précieuses et sensibles d’intégrer des algorithmes différentiellement privés dans leur architecture de données, offrant des garanties de confidentialité à leurs utilisateurs tout en effectuant une analyse significative des données.

Pour l’avenir

Les milieux de l’ingénierie et de la recherche ont tous deux des pistes pour avancer avec la confidentialité différentielle. Pour les ingénieurs, la tâche consiste à se former sur la confidentialité différentielle et à s’assurer qu’elle est utilisée le cas échéant pour la protection de la vie privée des utilisateurs. Pour les chercheurs, il s’agit de trouver davantage et de meilleurs algorithmes différentiellement privés, améliorant ainsi l’ensemble d’outils avec lesquels nous pouvons permettre l’analyse de données préservant la confidentialité.

Nous avons tous à gagner de la mise en place de garanties de confidentialité et des succès de l’analyse des données. Pour ces deux raisons, nous nous réjouissons à l’idée que de plus en plus d’organisations adoptent la protection différentielle de la vie privée.

À propos de l’auteur

Charlie Cabot est data scientist senior chez Privitar, une start-up de protection des données qui construit des logiciels hautes performances pour l’anonymisation des données, y compris des algorithmes de perturbation et de généralisation et des mécanismes différentiellement privés, pour faciliter l’utilisation en toute sécurité d’ensembles de données sensibles. Charlie se concentre sur les garanties de confidentialité prouvables et l’impact statistique de l’anonymisation sur l’analyse et la science des données. Auparavant, travaillant dans le domaine de la cybersécurité, Charlie a conçu des approches basées sur l’apprentissage automatique de la détection des logiciels malveillants et modélisé les cyberattaques sur les réseaux informatiques.