La k-anonymisation, ou parfois k-anonymité, est une propriété possédée par certaines données anonymisées. Le terme k-anonymisation ( en anglais) a été introduit pour la première fois par Pierangela Samarati et Latanya Sweeney dans un article publié en 1998., bien que le concept remonte à un article de 1986 de Tore Dalenius..

La k-anonymisation est une tentative pour résoudre le problème suivant : 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 , un , ou un . 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 enregistrements.

Voici une base de données non anonymisée des dossiers de patients d'un hôpital fictif. La colonne est un identifiant, et sont des quasi-identifiants, et est une valeur sensible non identifiante.

+ Patients traités dans l'étude le 30 avril 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 pour une certaine valeur de . 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 et toutes les valeurs de l'attribut par un . 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 de l'attribut peut être remplacée par , la valeur par

Voici la base de données anonymisée :

+ Patients traités dans l'étude le 30 avril 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 , et : 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 enregistrements pour un ensemble de données k-anonymes..

Critiques Cet exemple montre un échec de la k-anonymisation : d'autres enregistrements peuvent être reliés aux variables prétendument 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 et qu'il mesure 180 cm, on pourrait relier cette information à la base de données prétendument 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 , 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. Kenig et Tassa ont présenté un algorithme d'approximation pratique qui permet de résoudre le problème de -anonymisation avec une garantie d'approximation de l'ordre de ..

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 :

: cette attaque exploite le cas où toutes les valeurs d'une donnée sensible sont identiques dans un ensemble de enregistrements. Dans ce cas, même si les données ont été -anonymisées, la valeur sensible peut être prédite avec précision pour l'ensemble de enregistrements. : 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. : 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..

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..

On a également démontré que la -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.. 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..

Articles connexes Confidentialité différentielle

Notes et références

Catégorie:Vie privée Catégorie:Anonymat