Les mathématiques garantissent la confidentialité: une nouvelle approche de la sécurité des données

En 1997, lorsque les chercheurs médicaux du Massachusetts ont commencé à donner accès aux dossiers médicaux officiels, le gouvernement a supprimé les noms des patients, leurs adresses et leurs numéros de sécurité sociale des listes. William Weld, alors gouverneur, a assuré au public qu'il serait impossible de restaurer son identité sur rendez-vous.

Quelques jours plus tard, une lettre est arrivée au bureau de Weld envoyée par un étudiant du Massachusetts Institute of Technology. Des extraits de la carte médicale du gouverneur étaient joints à l'enveloppe.

Bien que les identifiants évidents aient été supprimés, les responsables ont décidé de laisser la date de naissance, le sexe et le code postal (code postal). Après avoir comparé ces données avec des enregistrements vocaux, Latanya Sweeney a pu calculer le dossier médical de Weld.

Le travail de Sweeney et d'autres percées dans la vie privée au cours des 15 dernières années soulèvent des problèmes de sécurité pour les données prétendument anonymes.

«Nous avons constaté que l'intuition des gens quant aux données à considérer comme privées ne fonctionne pas bien», explique Frank McSherry de Microsoft Research Silicon Valley. «Les ordinateurs améliorent constamment leur capacité à extraire des données individuelles d'un éventail d'informations que le profane considérerait comme sûres.»

L'étude de vos antécédents médicaux peut vous aider à trouver les gènes responsables du risque de maladie d'Alzheimer, à réduire le nombre d'erreurs dans les hôpitaux ou à trouver le meilleur médicament pour une maladie. La seule question est de savoir comment obtenir toutes ces données sans donner d'informations personnelles? Une étude de dix ans sur ce sujet approche déjà une solution universelle.

Cette approche est appelée «confidentialité différentielle» et vous permet de publier des données tout en protégeant les informations personnelles. L'algorithme de différenciation des données permet aux chercheurs de formuler toute requête dans une base de données contenant des informations sensibles et de recevoir une réponse «floue» de telle sorte qu'elle ne révèle aucune donnée personnelle - même la présence de données d'une personne spécifique dans cette base de données.

«L'idée est que vous pouvez laisser vos données être utilisées sans risque», explique Cynthia Dvork de Microsoft Research Silicon Valley. Dvork a introduit le concept de confidentialité différentielle (RP) en 2005 avec l'aide de McSherry, Cobby Nissim et Adam Smith.

La méthode conserve le droit à un «déni plausible», explique Avrim Blum de l'Université Carnegie Mellon. «Si je veux prétendre que mes informations personnelles sont différentes de ce que j'ai réellement, je peux le faire. La sortie du mécanisme RP dans la pratique ne différera pas beaucoup, peu importe si elle comprend le vrai ou le faux moi - donc je peux refuser tout ce que je veux. »

Un tel niveau élevé de confidentialité semble inaccessible. Et en fait, il n'y a pas d'algorithme RP utile qui produirait un résultat complètement identique lorsque vous fournissez vos données réelles ou fictives. Mais vous pouvez permettre aux algorithmes de produire des données presque identiques. Le degré de différence est calibré et représente une quantification de la vie privée. Les personnes ou les communautés peuvent décider quelle valeur de ce paramètre correspond à un degré acceptable de perte de confidentialité, puis choisir les algorithmes appropriés.

Les experts de la confidentialité ont développé une large gamme d'algorithmes RP pour traiter différentes données et répondre à différentes questions à leur sujet. La plupart du travail est difficile à percevoir par les personnes qui ne sont pas des experts dans le domaine.Par conséquent, les scientifiques développent des langages informatiques standardisés qui permettront non seulement aux experts de publier des données sensibles de la manière RP, simplement en écrivant un programme simple. «RP est une technologie prometteuse et très intéressante», explique Aaron Roth, spécialiste en informatique à l'Université de Pennsylvanie.


Le Comité de recensement OnTheMap utilise la confidentialité différentielle en publiant des données mais en ne divulguant pas d'informations personnelles

Aiguille dans une botte de foin

Il semble que pour résoudre les problèmes de confidentialité, il vous suffit de publier des données généralisées liées à de grands groupes de personnes. Mais même cette approche est lourde d'une violation de l'intégrité des données personnelles.

Supposons que vous ayez besoin de savoir si l'auteur est diabétique et que vous savez que mes données sont dans la base de données. On pourrait soustraire les résultats de deux requêtes: «combien de personnes ont le diabète dans la base de données» et «combien de personnes dans la base de données, avec un nom autre qu'Eric Clarreich, ont le diabète».

La combinaison de deux de ces requêtes viole ma vie privée. Mais il n'est pas toujours clair quelles combinaisons particulières de questions peuvent porter atteinte à la vie privée. Trouver de telles combinaisons est une tâche NP-complète, c'est-à-dire qu'il n'existe pas d'algorithme informatique efficace pour suivre de telles «attaques».

En 2008, les chercheurs ont montré le danger de publier les informations agrégées obtenues de la recherche génétique générale - l'un des principaux outils pour découvrir la dépendance du diabète vis-à-vis des gènes. Ces études impliquent le décodage des gènes du groupe test de 100 à 1 000 patients atteints de la même maladie, puis le calcul de la fréquence moyenne avec laquelle l'une des 100 000 mutations se produit. Si l'une des mutations survient beaucoup plus souvent dans le groupe, elle est notée comme potentiellement associée à la maladie.

Une équipe de chercheurs dirigée par Niels Homer, qui était un étudiant diplômé à l'Université de Californie à l'époque, a montré que dans de nombreux cas, connaissant le génome du patient, vous pouvez voir s'il faisait partie du groupe de test du génome. Après cela, l'association des instituts médicaux a révoqué le décret de publication des données obtenues lors des études génétiques.

Les chercheurs ont fait une conclusion encore plus surprenante en 2011 - il est possible d'extraire des informations personnelles sur les achats, guidé par un système de recommandation avec Amazon, qui donne des résultats comme «qui a acheté et aussi acheté B et C». En observant les changements dans les recommandations et en les comparant avec les avis que les gens font sur les articles achetés, dans plusieurs cas, les chercheurs ont pu dire qu'un acheteur particulier avait acheté un article particulier un jour donné - avant même qu'il ne publie un avis sur cet article.

Dans tous les cas, les mesures de confidentialité semblent adéquates, tant qu'elles ne sont pas suffisantes. Mais déjà à cette époque, une nouvelle approche de la protection de la vie privée était en préparation, obtenue en recherchant la réponse à la question principale: que signifie protéger la vie privée?

L'intimité de deux mondes

Si les chercheurs examinent la base de données des patients et trouvent un lien entre le tabagisme et une certaine forme de cancer, la confidentialité différentielle ne protégera pas une personne qui fume dans un lieu public de l'étiquette d'une personne présentant un risque accru de tomber malade. Mais si fumer est le secret d'une personne, caché dans la base, RP la protégera.

«Différence» signifie prendre en compte la différence de deux mondes: dans l'un d'eux, vous autorisez à inclure vos données personnelles dans la base de données et dans l'autre, vous ne le permettez pas. Les deux mondes ne seront pas absolument identiques, mais ils peuvent être rendus aussi similaires que possible, et il sera presque impossible de les distinguer. C'est le but du RP.

RP se concentre sur les algorithmes qui émettent des données, reçoivent des requêtes dans la base de données et émettent des réponses - pas exactes, mais modifiées au hasard. Si vous posez la même question sur deux bases qui ne diffèrent que par les données d'une personne, vous obtiendrez essentiellement les mêmes réponses.


Représentation RP de l'emplacement des utilisateurs à la recherche du mot "cricket" dans un moteur de recherche

Plus précisément, pour toute réponse possible, la probabilité de sa réception devrait être la même pour les deux bases de données; le rapport de ces deux probabilités doit être limité à un nombre R proche de l'unité. Plus R est proche de 1, plus il est difficile pour un attaquant de savoir s'il reçoit des informations de la base A ou de la base B, et plus la personne X sera protégée. Puisque si l'attaquant ne peut pas savoir si les informations reçues par lui incluent des informations sur X, il ne pourra pas comprendre quelles données se réfèrent à X. Les

chercheurs de RP parlent généralement du logarithme de R et le désignent par Ɛ. Le paramètre quantifie la fuite de données personnelles. Plus Ɛ près de zéro, mieux l'algorithme protège la confidentialité.

Pour comprendre comment l'algorithme RP peut être construit, regardons l'exemple le plus simple d'un tel algorithme. Il utilise un scénario dans lequel le questionneur ne peut faire que des requêtes quantitatives. Par exemple: "combien de personnes dans la base de données ont la propriété C?"

Supposons que la vraie réponse à l'une des questions soit 157. L'algorithme RP y ajoutera du «bruit» - avant d'émettre une réponse, ajoutez ou soustrayez un nombre aléatoire. Par conséquent, nous obtenons 153, 159 ou 292. Le questionneur connaît la distribution de probabilité utilisée par l'algorithme, donc il sait à quel point le résultat réel est déformé (sinon le retour serait complètement inutile). Mais quel type de nombre aléatoire a été ajouté à la réponse, il ne le sait pas.

La formule de distribution doit être choisie avec soin. Pour comprendre quelle distribution garantit la confidentialité, imaginons qu'un demandeur persistant essaie de savoir si je suis dans la base de données. Il demande: "Combien de personnes nommées Eric Clarreich sont dans la base de données?" Supposons qu'il reçoive une réponse de 100. Comme ce nom est rare, il se rend compte que la réponse était en fait 0 ou 1. Il a deux possibilités:

A) la réponse est 0, et l'algorithme a ajouté 100 comme bruit;
B) la réponse est 1, et l'algorithme ajouté 99 La

probabilité de choisir 100 et 99 devrait être la même. L'intervenant ne peut alors pas distinguer entre ces deux cas. Plus précisément, le rapport de ces deux probabilités ne doit pas dépasser un R. prédéterminé et une telle condition doit être préservée non seulement pour les paires 100 et 99, mais aussi pour deux nombres consécutifs quelconques.

Cette propriété a la distribution Laplace. Son pic pointu tombe à zéro, puis le graphique diminue progressivement dans les deux sens. Pour cela, la condition d'existence du nombre R (largeur de distribution) est remplie, de telle sorte que pour deux nombres consécutifs quelconques, le rapport de leurs probabilités est R.

Pour chaque largeur, il existe une distribution de Laplace possible. Par conséquent, vous pouvez jouer avec la largeur pour obtenir une distribution qui fournit exactement le degré d'intimité dont nous avons besoin. Pour une intimité forte, la distribution sera relativement large et plate. Les nombres loin de 0 tomberont avec presque la même probabilité que les nombres proches de zéro. Les données seront beaucoup floues.

Naturellement, il y a une confrontation entre la vie privée et l'utilité. Plus vous avez besoin d'intimité, plus vous devez ajouter de bruit et moins la réponse sera utile. Lorsque vous utilisez la distribution de Laplace, la quantité de bruit ajouté est de retour Ɛ. Si le paramètre de confidentialité est 0,01, l'algorithme rendra les indicateurs quantitatifs d'environ 100.

Plus l'ensemble de données est grand, moins le flou donné affectera l'utilitaire. Dans une base de données de centaines d'enregistrements, un flou de 100 interfère plus que dans une base de données de millions d'enregistrements. Selon Dvork, pour des données à l'échelle d'Internet, c'est-à-dire des centaines de millions, l'algorithme fournit déjà une confidentialité suffisante pour une utilisation pratique.

Et le «bruit» selon Laplace n'est que la première étape de la mise en œuvre du RP. Les chercheurs ont déjà mis au point un grand nombre d'algorithmes beaucoup plus complexes, pour beaucoup desquels le rapport de l'utilité et de la confidentialité dépasse celui de Laplace dans certaines situations.

«Les gens trouvent toujours des moyens de s'améliorer, et il y a encore place à l'amélioration», explique Dvork. En ce qui concerne les ensembles de données plus modestes qu'Internet, a-t-elle déclaré, "il existe des algorithmes pour de nombreuses tâches".

Avec l'algorithme RP, il n'est pas nécessaire d'analyser soigneusement les problèmes de violation de la vie privée - cette protection est déjà intégrée à l'algorithme. Étant donné que les questions qui interfèrent avec leurs propres affaires se résument généralement à de petits nombres liés à des personnes spécifiques, et que les questions de nature différente étudient le comportement de grands groupes, la quantité de bruit supplémentaire qui annule les caractéristiques individuelles aura peu d'effet sur les réponses aux questions légitimes.

Avec RP, les problèmes des chercheurs de données, tels que les comparaisons croisées avec des sources externes, disparaissent. L'approche mathématique ne s'attend pas à ce que l'attaquant ait des sources limitées d'informations externes.

«L'approche RP implique que l'attaquant est tout-puissant», explique McSherry. - Même si l'attaquant revient après 100 ans, accumulant constamment des idées et des technologies informatiques, il ne pourra toujours pas savoir si vous êtes dans la base de données. RP est protégé de l'avenir. "

Primitive fondamentale

Jusqu'à présent, nous avons envisagé une situation dans laquelle quelqu'un interroge la base de données avec un numéro comme réponse. Mais la réalité est plus compliquée. Les chercheurs veulent poser beaucoup de questions à la base de données. Et au fil du temps, des éléments de vos informations personnelles se retrouveront dans diverses bases de données, chacune fournissant des données sans demander au reste.

RP fournit un moyen précis et facile d'évaluer la menace globale à la vie privée lorsque les chercheurs posent plusieurs questions à toutes les bases de données dans lesquelles vos données sont présentes. Supposons que si vos données se trouvent dans deux bases de données et que ces données soient fournies selon des algorithmes qui fournissent les paramètres de confidentialité Ɛ1 et Ɛ2, la quantité totale d'informations personnelles divulguées ne sera pas supérieure à Ɛ1 + Ɛ2. La même formule fonctionne pour une seule base de données avec plusieurs requêtes. Pour m requêtes, la fuite sera limitée au-dessus de m * Ɛ.

En théorie, un conservateur de base de données peut permettre aux chercheurs de poser autant de questions qu'ils le souhaitent, en ajoutant la quantité nécessaire de bruit de Laplace à chaque réponse afin que la quantité totale de données personnelles divulguées ne dépasse pas une certaine limite.

Il s'avère que la limite des réponses numériques n'est pas si critique. De nombreuses autres requêtes peuvent être modifiées pour devenir quantitatives. Par exemple, si vous devez créer une liste de centaines de noms les plus populaires pour les bébés nés en 2012, vous pouvez, par exemple, poser une séquence de questions comme «Combien d'enfants ont reçu des noms commençant par A?» Et traiter les résultats.

"L'un des premiers résultats de l'apprentissage automatique affirme que tout ce qui peut être appris en principe peut être appris à l'aide de requêtes numériques", explique Aaron Roth. «De telles demandes ne sont pas des jouets en soi, mais une primitive fondamentale», c'est-à-dire des briques, sur la base desquelles des algorithmes plus complexes peuvent être construits.

Mais il y a un hic. Plus nous pouvons permettre de poser de questions, plus de bruit sera ajouté à chaque réponse. Regardons un exemple avec des noms. Si nous décidons de limiter la dépense maximale de confidentialité Ɛ à 0,01, et que les noms seront de 10 000, la limite de confidentialité pour chaque problème sera de Ɛ / 10 000, ou 0,000001. Le niveau de bruit sera de 10 000 / Ɛ ou 1 000 000 - et ce niveau élimine simplement les résultats réels.

En d'autres termes, l'approche «frontale» avec l'ajout de bruit de Laplace à chaque réponse est limitée par le nombre de questions possibles. Pour remédier à la situation, les programmeurs ont dû développer des primitives plus adaptées - des «briques» algorithmiques, à l'aide desquelles, étant donné la structure d'une base et d'une tâche spécifiques, elles peuvent répondre à plus de questions avec plus de précision.

Par exemple, en 2005, Smith a découvert que la tâche avec les noms avait une structure spéciale: la suppression d'informations sur une personne de la base de données modifie la réponse pour un seul nom sur 10 000. Par conséquent, nous ne pouvons pas ajouter plus de 1 / Ɛ de bruit à chaque réponse, au lieu de 10 000 / Ɛ, et la confidentialité de la réponse restera dans notre limite de . Une telle primitive peut être appliquée à n'importe quelle requête «histogramme» - c'est-à-dire une requête sur le nombre de personnes tombant dans l'une des nombreuses catégories mutuellement exclusives, telles que les noms.

Lorsque Smith en a parlé au Dwork, «quelque chose en moi s'est réjoui», dit le Dwork. «J'ai réalisé que nous pouvons utiliser la structure de la demande ou du calcul et obtenir une précision beaucoup plus grande de la réponse.»

Depuis lors, les informaticiens ont développé une grande bibliothèque de ces primitives. Et puisque la règle additive explique ce qui arrive à la confidentialité lors de la combinaison d'algorithmes, les programmeurs peuvent assembler ces «briques» dans des structures complexes, tout en surveillant la restriction des fuites de confidentialité.

Pour simplifier l'accès au système RP pour les personnes qui ne sont pas des experts, plusieurs groupes travaillent sur la création d'un langage de programmation qui nous permettra de faire abstraction des fondements mathématiques des algorithmes.


PINQ - l'un des exemples de PL pour RP

Les langages de programmation pour travailler avec la confidentialité différentielle, tels que PINQ, fournissent une interface pour les données sensibles et vous permettent de poser des questions à leur sujet, en peaufinant les réponses pour protéger la confidentialité. «Si vous êtes en charge d'un ensemble de données, vous n'avez pas à vous soucier de ce que les gens en font pendant que leurs demandes sont faites en utilisant ce PL», explique McSherry, qui a créé le langage PINQ. "Le programme garantit la sécurité des requêtes."

Ressource non renouvelable

Étant donné que la règle additive simple pour Ɛ définit la limite supérieure exacte de la perte de confidentialité lorsque différentes bases de données contenant vos données fournissent des réponses aux requêtes, cette règle, selon McSherry, transforme la confidentialité en monnaie.

Par exemple, si vous décidez quelle restriction à la perte de la vie privée pour vous personnellement est acceptable pour toute votre vie, vous pouvez alors décider de "dépenser" cette vie privée - échanger de l'argent ou soutenir un bon projet de recherche. Chaque fois que vous autorisez l'utilisation de vos données dans une nouvelle publication d'informations, vous saurez quel est l'équilibre de votre «budget» de confidentialité.

Et le conservateur de l'ensemble de données peut décider comment dépenser la quantité de confidentialité qu'il a décidé de divulguer - par exemple, considérer les propositions de projets de recherche qui décrivent non seulement les demandes disponibles, mais aussi la quantité de confidentialité utilisée dans les projets. Le conservateur pourra alors choisir les projets qui utiliseront le mieux le «budget» existant de cet ensemble d'informations. Une fois le budget dépensé, l'ensemble de données est fermé.

«La confidentialité est une ressource non renouvelable», explique McSherry. "Dès que vous le dépensez, il disparaît."

Lorsqu'on lui a demandé quelle valeur Ɛ représente une restriction acceptable à la perte de vie privée, la société devrait répondre, pas les programmeurs. Et chacun peut avoir sa propre réponse. Et bien que la perspective d'attribuer un prix à une chose intangible comme la vie privée puisse sembler intimidante, des analogues existent déjà.

«Il existe une autre ressource ayant les mêmes propriétés - l'horloge de votre vie», explique McSherry. "Leur nombre est limité, et après les avoir dépensés, ils disparaissent." Mais comme nous avons une monnaie et un marché du travail, notre société a trouvé comment attribuer un prix au temps humain. On peut imaginer comment la même chose se produira avec la vie privée. »

Source: https://habr.com/ru/post/fr398011/