Tout sur l’anonymat 2/4 : Tout savoir sur le k-anonymat

Introduction

Contexte

Cette série d’articles est inspirée du cours Privacy, Data Protection, Security, par Benjamin Nguyen, que j’ai suivi lors de l’école d’été Responsabilité des Algorithmes : enjeux sociétaux et environnementaux organisée par les groupes de recherche Recherche Opérationnelle et Intelligence Artificielle du CNRS en 2023.

Ce second article concerne le premier algorithme proposé pour anonymiser les données : le k-anonymat, théorisé en 1997 par Latanya Sweeney et présenté formellement dans un article en 2002.

Rappel : anonymat syntaxique et anonymat sémantique

Le processus d’anonymisation a pour but d’empêcher la ré-identification des données (associer une observation à une personne), et la divulgation de données sensibles (origine sociale ou ethnique, religion, dossier médical…). Bien que ces deux finalités soient similaires, un algorithme d’anonymisation des données peut parfois atteindre l’un sans atteindre l’autre : pour récupérer une donnée sensible, il suffit parfois d’identifier à quel groupe d’observations appartient un individu, sans nécessairement retrouver l’observation exacte qui lui correspond.

On divise globalement les méthodes d’anonymisation en deux groupes : le premier est l’anonymat syntaxique, qui concerne les données en elles-mêmes, et considère un jeu de données comme anonyme s’il obéit à un certain nombre de contraintes pré-établies. L’anonymat sémantique, quant à lui, se concentre sur le processus de collecte et de publication des données.

Un algorithme d’anonymisation syntaxique : le k-anonymat

Présentation

Considérons un jeu de données, contenant des observations sur N individus (une observation correspond à un individu). On regroupe les variables associées à chaque observation en trois groupes :

• les données identifiantes, qui sont liées à un individu de manière unique
• les données quasi-identifiantes, qui ne permettent pas d’identifier un individu prises isolément, mais qui le permettent lorsqu’on les groupe
• les données non-identifiantes

Un jeu de données est considéré comme k-anonyme lorsque chaque combinaison de quasi-identifiants correspond à au moins k observations. La méthode la plus simple pour rendre un jeu de données k-anonyme est de procéder par agrégations successives.

Exemple : (Note: L’exemple suivant est tiré, avec quelques modification, du livre The Ethical Algorithm, par Kearns et Roth). Ce jeu de données fictif est publié par un hôpital :

Même en supposant que les prénoms aient été effacés du dataset, n’importe qui connaissant l’âge et le genre d’un patient pourra retrouver le résultat de son diagnostic.

On peut donc commencer par remplacer l’âge précis par une plage de 10 ans, afin de brouiller les pistes. En réordonnant les lignes pour faire apparaître les groupes plus facilement, on obtient les données suivantes :

Ici, chaque combinaison d’âge et de genre correspond à au moins deux individus : le jeu de données est 2-anonyme. On ne peut donc plus retrouver le diagnostic précis d’un patient à partir de son âge et de son genre : la ré-identification précise est impossible, on a toujours au mieux une chance sur deux de retrouver l’observation correspondant à une personne dont on connaît l’âge et le genre. Pour aller plus loin dans l’anonymat, on pourrait faire des plages d’âges plus grandes, ou supprimer l’information du genre en réunissant les deux catégories.

Avantages et inconvénients

Les avantages :

• Simplicité : C’est son point fort. Le k-anonymat est une notion facile à comprendre et à expliquer, et son implémentation est relativement simple. Le risque de ré-identification est facile à quantifier (chaque observation a un risque de ré-identification égal au maximum à 1/k).

Les inconvénients :

• Définition des quasi-identifiants : Dans le tableau ci-dessus, sur les deux femmes d’entre 30 et 39 ans, une seule fume, donc si on connaît l’âge, le genre et le statut de fumeur de notre patiente, on pourrait bien réussir à ré-identifier son dossier médical. Devrait-on considérer l’attribut “fumeur” comme un quasi-identifiant ?
• Divulgation des données sensibles : si on ne peut pas ré-identifier directement une observation, on peut parfois inférer certaines données en fonction du groupe auquel appartient l’individu. Par exemple, dans le tableau ci-dessus, si on sait qu’Eugène est un homme d’entre 20 et 29 ans, il a deux chances sur trois d’avoir attrapé le covid, et une chance sur trois de souffrir de la maladie de Lyme. Les deux hommes de la catégorie d’âge ([30–39]) et de genre sont fumeurs, donc si l’on connaît un patient de ce groupe, on sait qu’il fume. Les attaques cherchant à exploiter cette faille sont connues sous le nom d’attaques d’homogénéité.
• Risque de ré-identification par croisement : l’un des inconvénients majeurs du k-anonymat est sa vulnérabilité à un attaquant possédant des connaissances externes au jeu de données, et en particulier en cas de publication d’autres données. Imaginons qu’un second hôpital (ou le même hôpital quelques mois plus tard) publie de nouvelles données, et que nous sachions qu’Eugène est retourné à l’hôpital dans cet intervalle.

En croisant le tableau ci-dessus avec le précédent, on constate que la seule ligne identique dans les deux tableaux est celle du patient atteint de la maladie de Lyme. Nous avons retrouvé l’observation correspondant à Eugène !

Renforcer la robustesse du k-anonymat : l-diversité et t-proximité

Le k-anonymat souffre donc de plusieurs failles qui peuvent entraîner la divulgation de données sensibles et/ou personnelles. Il existe cependant diverses méthodes qui permettent d’en renforcer la robustesse :

l-diversité

Définition

La l-diversité, proposée en 2006 par Machanavajjhala, Gehrke, Kifer, et Venkitasubramaniam, est une contrainte supplémentaire sur le dataset k-anonymisé, qui vise à parer aux attaques d’homogénéité en spécifiant la distribution des valeurs sensibles au sein de chaque classe d’équivalence (collection d’observations ayant les mêmes quasi-identifiants après anonymisation). Il existe grosso modo trois manières de l’implémenter :

• La plus simple, la l-diversité distincte, impose que chaque classe d’équivalence contienne au moins l valeurs distinctes de la valeur sensible considérée. Dans notre exemple ci-dessus, on souhaite donc que pour une même classe d’âge et un même genre, on ait au moins l diagnostic différents possibles.
• Plus complexe, la l-diversité entropique impose une certaine distribution des valeurs sensibles au sein de chaque classe ; cette condition fait appel à la notion d’entropie en théorie de l’information, qui quantifie le taux d’information gagnée par l’observation d’une variable. On dit qu’un jeu de données satisfait la l-diversité entropique si pour tout attribut sensible s, et tout groupe de quasi-identifiants généralisés q* :

• Enfin, la (l,c)-diversité récursive, plus simple, impose que la fréquence de la valeur la plus représentée ne soit pas trop élevée, et que la fréquence des valeurs les moins représentées ne soit pas trop basse. Plus précisément, dans une même classe d’équivalence, on compte le nombre de fois que chaque valeur sensible apparaît, et on appelle ces décomptes r1, r2, … r_m, organisés par ordre décroissant. Alors on dit qu’un jeu de données satisfait la (l,c)-diversité récursive si, pour chaque classe d’équivalence :

Limites

La l-diversité permet donc de s’assurer qu’un attribut sensible ne sera pas révélé à un adversaire un peu trop curieux. Elle possède cependant des limites, mises en évidence par Li, Li et Venkatasubramanian en 2007.

La l-diversité peut être difficile à implémenter, sans être toujours nécessaire. Imaginons qu’un jeu de données de santé donne les informations de diagnostic d’une maladie rare, qui touche seulement 1% des 10 000 patients présents dans les données. La l-diversité traite le diagnostic positif comme aussi sensible que le diagnostic négatif, mais en pratique, le fait de révéler qu’un patient a reçu un diagnostic négatif a peu d’impact : le patient fait partie d’une large majorité de la population. En outre, seulement 10 000 x 1% = 100 diagnostics positifs sont présents dans le jeu de données, donc si l’on veut que chaque classe d’équivalence possède au moins un diagnostic positif et un négatif, on aura au maximum 100 classes. C’est trop peu pour extraire des informations pertinentes des données.

En outre, dans le cas d’une distribution déséquilibrée comme ci-dessus, la l-diversité peut s’avérer insuffisante pour protéger les informations sensibles. Une classe d’équivalence qui contiendrait 50% de diagnostics positifs et négatifs satisferait la 2-diversité selon les trois définitions ci-dessus (distincte, entropique, et récursive pour n’importe quel c). Cependant, un patient membre de cette classe aurait 50% de chances d’avoir obtenu un diagnostic positif, une statistique bien supérieure à la distribution générale de 1%. De même pour une classe contenant 49 diagnostics positifs et 1 diagnostic négatifs (qui satisferait alors les 2-diversités distincte et entropique), dans laquelle un patient aurait 98% de chances d’avoir été diagnostiqué positif.

t-proximité

Définition

Pour parer aux limites de la l-diversité, les auteurs proposent la notion de t-proximité, qui répond à la question suivante : quelle quantité d’information apporte le fait de connaître les quasi-identifiants d’une personne ? En effet, la publication d’un jeu de données, même complètement anonymisé (sans aucun quasi-identifiants), révèle en lui-même certaines informations. Par exemple, dans l’exemple précédent, même sans rien savoir des personnes présentes dans le jeu de données, on sait qu’elles ont 1% de chances d’avoir un diagnostic positif. On ne peut pas contrôler cette information : cela reviendrait à ne pas publier le jeu de données du tout. On cherche donc, avec la t-proximité, à agir sur la quantité d’information que l’on peut contrôler : celle qui est révélée lorsque l’on connaît les quasi-identifiants d’une personne, et qu’on peut retrouver sa classe d’équivalence dans le jeu de données anonymisé. Cela nous mène à la définition suivante :

Un jeu de données satisfait la t-proximité si, pour chaque classe d’équivalence, la distance entre la distribution des valeurs d’un attribut sensible au sein de la classe et la distribution au sein du jeu de données en entier ne dépasse pas une limite t.

La notion de distance utilisée pour mesurer la t-proximité est la distance du cantonnier (ou distance du terrassier, Earth Mover’s Distance en anglais). Contrairement aux distances “classiques”, qui prennent uniquement en compte la différence de probabilité entre chaque classe, la distance du cantonnier mesure aussi la distance entre les valeurs de chaque classe. Par exemple, dans le cas où notre attribut sensible serait un salaire, une classe dont tous les salaires sont très inférieurs à la moyenne aurait une distance plus élevée à la distribution globale qu’une classe où tous les salaires sont autour de la moyenne, même si les salaires individuels présents dans chaque classe ont la même distribution que dans la population globale.

Limites

Si la distance du cantonnier mesure plutôt adéquatement la distance entre deux distributions, elle n’a que peu de rapport avec le gain d’information réel qu’un observateur obtient en connaissant les quasi-identifiants d’un membre du dataset. La l-diversité est plus précise dans ce cas.

En outre, la t-proximité peut être compliquée à implémenter, puisqu’elle nécessite que les attributs sensibles soient distribués d’une certaine manière dans les données.

Conclusion

Depuis sa théorisation en 1997 par Latanya Sweeney, le k-anonymat a connu un franc succès, et il est toujours utilisé aujourd’hui pour anonymiser des données personnelles. Plusieurs auteurs ont, par la suite, proposé des contraintes supplémentaires qui peuvent être appliquées au jeu de données afin d’en renforcer la robustesse. Au regard du RGPD, un dataset k-anonymisé est souvent considéré comme suffisamment anonyme pour être conservé sans risque pour les personnes dont les données sont concernées.

Le k-anonymat n’est cependant pas sans limites ; en particulier, un jeu de données peut s’avérer vulnérable dans le temps, puisque la publication ultérieure d’autres données peut en compromettre l’anonymat.

Remerciement

Merci à nos collègues Alexandre DO et Lu WANG pour la revue de l’article.

A propos de l’auteur

Après un doctorat en mathématiques fondamentales, Béatrice CHETARD a rejoint La Javaness en tant que data scientist en mars 2021. Elle s’intéresse à tous les aspects de la data science (données structurées, NLP, computer vision), et tout particulièrement aux question d’éthique et de responsabilité des algorithmes.