K-anonymisation
La k-anonymisation est une propriété possédée par certaines données anonymisées. Le terme k-anonymisation (Modèle:Lang en anglais) a été introduit pour la première fois par Pierangela Samarati et Latanya Sweeney dans un article publié en 1998[1], bien que le concept remonte à un article de 1986 de Tore Dalenius[2].
La k-anonymisation est une tentative pour résoudre le problème suivant : Modèle:Citation Une diffusion de données est dite k-anonyme si les informations publiées relatives à chaque personne ne peuvent pas être distinguées d'au moins personnes dont les informations sont également publiées. Malheureusement, les garanties fournies par le k-anonymat sont ambitieuses et non mathématiques.
Méthodes
Pour traiter un ensemble de données au moyen de la k-anonymisation afin de pouvoir les publier tout en protégeant la vie privée, un scientifique des données doit d'abord examiner l'ensemble de données et décider si chaque attribut (colonne) est un Modèle:Citation, un Modèle:Citation, ou un Modèle:Citation. Les identifiants tels que les noms sont supprimés, les valeurs non identifiantes sont conservées et les quasi-identifiants seront traités de sorte que chaque combinaison distincte de quasi-identifiants désigne au moins Modèle:Citation enregistrements.
Voici une base de données non anonymisée des dossiers de patients d'un hôpital fictif. La colonne Modèle:Citation est un identifiant, Modèle:Citation et Modèle:Citation sont des quasi-identifiants, et Modèle:Citation est une valeur sensible non identifiante.
| Nom | Âge | Genre | Hauteur | Poids | État du domicile | Religion | Maladie |
|---|---|---|---|---|---|---|---|
| Ramcha | 30 | Femme | 165 cm | 72 kg | Tamil Nadu | Hindou | Cancer |
| Yadu | 24 | Femme | 162 cm | 70 kg | Kerala | Hindou | Infection virale |
| Salima | 28 | Femme | 170 cm | 68 kg | Tamil Nadu | Musulman | Tuberculose |
| Sunny | 27 | Homme | 170 cm | 75 kg | Karnataka | Parsi | Pas de maladie |
| Jeanne | 24 | Femme | 165 cm | 71 kg | Kerala | Chrétien | Lié au cœur |
| Bahuksana | 23 | Homme | 160 cm | 69 kg | Karnataka | Bouddhiste | Tuberculose |
| Rambha | 19 | Homme | 167 cm | 85 kg | Kerala | Hindou | Cancer |
| Kishor | 29 | Homme | 180 cm | 81 kg | Karnataka | Hindou | Lié au cœur |
| Johnson | 17 | Homme | 175 cm | 79 kg | Kerala | Chrétien | Lié au cœur |
| John | 19 | Homme | 169 cm | 82 kg | Kerala | Chrétien | Infection virale |
Ces données contiennent 6 attributs et 10 enregistrements. Il existe deux méthodes courantes pour atteindre le Modèle:Citation pour une certaine valeur de Modèle:Citation.
- Suppression : Dans cette méthode, certaines valeurs des attributs sont remplacées par un astérisque '*'. Dans le tableau anonymisé ci-dessous, nous avons remplacé toutes les valeurs de l'attribut Modèle:Citation et toutes les valeurs de l'attribut Modèle:Citation par un Modèle:Citation.
- Généralisation : Dans cette méthode, les valeurs individuelles des attributs sont remplacées par une catégorie plus large. Par exemple, la valeur Modèle:Citation de l'attribut Modèle:Citation peut être remplacée par Modèle:Citation, la valeur Modèle:Citation par Modèle:CitationModèle:Etc.
Voici la base de données anonymisée :
| Nom | Âge | Genre | Hauteur | Poids | État de domicile | Religion | Maladie |
|---|---|---|---|---|---|---|---|
| * | 20 < Âge ≤ 30 | Femme | 165 cm | 72 kg | Tamil Nadu | * | Cancer |
| * | 20 < Âge ≤ 30 | Femme | 162 cm | 70 kg | Kerala | * | Infection virale |
| * | 20 < Âge ≤ 30 | Femme | 170 cm | 68 kg | Tamil Nadu | * | Tuberculose |
| * | 20 < Âge ≤ 30 | Homme | 170 cm | 75 kg | Karnataka | * | Pas de maladie |
| * | 20 < Âge ≤ 30 | Femme | 165 cm | 71 kg | Kerala | * | Lié au cœur |
| * | 20 < Âge ≤ 30 | Homme | 160 cm | 69 kg | Karnataka | * | Tuberculose |
| * | Âge ≤ 20 | Homme | 167 cm | 85 kg | Kerala | * | Cancer |
| * | 20 < Âge ≤ 30 | Homme | 180 cm | 81 kg | Karnataka | * | Lié au cœur |
| * | Âge ≤ 20 | Homme | 175 cm | 79 kg | Kerala | * | Lié au cœur |
| * | Âge ≤ 20 | Homme | 169 cm | 82 kg | Kerala | * | Infection virale |
Ces données sont 2-anonymes en ce qui concerne les attributs Modèle:Citation, Modèle:Citation et Modèle:Citation : il y a toujours au moins 2 lignes contenant exactement toute combinaison de valeurs de ces attributs figurant dans le tableau. Les attributs disponibles pour un consommateur sont appelés quasi-identifiants. Chaque tuple de quasi-identifiant apparaît dans au moins Modèle:Citation enregistrements pour un ensemble de données k-anonymes[3].
Critiques
Cet exemple montre un échec de la k-anonymisation : d'autres enregistrements peuvent être reliés aux variables prétendûment non identifiantes. Par exemple, si l'on peut obtenir dans le cadre de l'étude l'agenda de la personne qui prenait des signes vitaux et qu'on apprend ainsi que Kishor était à l'hôpital le 30 avril et qu'il mesure 180 cm, on pourrait relier cette information à la base de données prétendûment anonymisée (qui a peut-être été publiée sur Internet) et en déduire que Kishor souffre d'une maladie cardiaque. Si l'on est au courant de la visite de Kishor à l'hôpital le 30 avril, on pourrait le déduire en sachant simplement que Kishor mesure 180 cm, qu'il pèse environ 80 à 82 kg et qu'il vient du Karnataka.
Ce problème se trouve au cœur de la k-anonymisation : on ne peut pas déterminer mathématiquement et sans ambiguïté si un attribut est un identifiant, un quasi-identifiant ou une valeur sensible non identifiante. En fait, toutes les valeurs sont potentiellement identifiantes, en fonction de leur prépondérance dans la population et des informations supplémentaires dont dispose le consommateur des données. D'autres mécanismes de confidentialité tels que la confidentialité différentielle ne partagent pas ce problème.
Meyerson et Williams (2004) ont démontré qu'optimiser la k-anonymisation est un problème NP-difficile, mais les méthodes heuristiques telles que k-Optimize, fournies par Bayardo et Agrawal (2005) donnent souvent des résultats efficaces[4]Modèle:,[5] Kenig et Tassa ont présenté un algorithme d'approximation pratique qui permet de résoudre le problème de Modèle:Citation-anonymisation avec une garantie d'approximation de l'ordre de [6].
Attaques
Bien que la k-anonymisation soit une approche relativement simple à mettre en œuvre pour anonymiser un ensemble de données avant sa publication, il est vulnérable à de nombreuses attaques. Lorsqu'un agresseur dispose par ailleurs de certaines informations, ces attaques deviennent encore plus efficaces. Elles comprennent :
- Modèle:Citation : cette attaque exploite le cas où toutes les valeurs d'une donnée sensible sont identiques dans un ensemble de Modèle:Citation enregistrements. Dans ce cas, même si les données ont été Modèle:Citation-anonymisées, la valeur sensible peut être prédite avec précision pour l'ensemble de Modèle:Citation enregistrements.
- Modèle:Citation : cette attaque exploite une association entre un ou plusieurs attributs de quasi-identifiant avec l'attribut sensible afin de réduire l'ensemble des valeurs possibles pour l'attribut sensible. Par exemple, Machanavajjhala, Kifer, Gehrke et Venkitasubramaniam (2007) ont montré que le fait de savoir que les crises cardiaques surviennent à un rythme réduit chez les patients japonais pouvait être utilisé pour réduire la plage de valeurs d'un attribut sensible de la maladie d'un patient.
- Modèle:Citation : Cette attaque, introduite en 2022 par Aloni Cohen, tire parti de la façon dont les algorithmes d'anonymisation agrègent les attributs dans différents enregistrements. Étant donné que l'agrégation est déterministe, il est possible, dans de nombreux cas, de reconstituer l'image des données d'origine qui auraient dû être protégées. Cette attaque est facilitée si l'agresseur dispose d'informations complémentaires, mais elles ne sont pas indispensables[7].
Comme la k-anonymisation n'implique aucune randomisation, les attaquants peuvent faire des inférences fiables et incontestables sur des données susceptibles de nuire aux individus. Par exemple, si l'on sait que John, 19 ans, originaire du Kerala, figure dans la base de données ci-dessus, on peut dire avec certitude qu'il a soit un cancer, soit une maladie cardiaque, soit une infection virale. La k-anonymisation est une mauvaise méthode pour anonymiser des jeux de données de grande dimension[8].
On a également démontré que la Modèle:Citation-anonymisation peut fausser les résultats d'un ensemble de données s'il supprime et généralise de manière disproportionnée des points de données présentant des caractéristiques non représentatives[9]. On peut cependant modifier les algorithmes de suppression et de généralisation qu'utilise la k-anonymisation afin qu'ils ne présentent pas ce biais[10].