K-anonymisation

Un article de Wikipédia, l'encyclopédie libre.
Si ce bandeau n'est plus pertinent, retirez-le. Cliquez ici pour en savoir plus.
Si ce bandeau n'est plus pertinent, retirez-le. Cliquez ici pour en savoir plus.

Cet article est orphelin. Moins de trois articles lui sont liés ().

Vous pouvez aider en ajoutant des liens vers [[K-anonymisation]] dans les articles relatifs au sujet.

La k-anonymisation est une propriété possédée par certaines données anonymisées. Le terme k-anonymisation (k-anonymity 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 : « Soient des données spécifiques à des personnes physiques et structurées sous forme de champs, produire une publication des données avec des garanties scientifiques que les individus qui sont sujets des données ne puissent pas être ré-identifiés tout en gardant en pratique l'utilité des données[3],[4],[5]. » 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[modifier | modifier le code]

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 « identifiant », un « non-identifiant », ou un « quasi-identifiant ». 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 « k » enregistrements.

Voici une base de données non anonymisée des dossiers de patients d'un hôpital fictif. La colonne « Nom » est un identifiant, « Âge, sexe, état du domicile » et « Religion » sont des quasi-identifiants, et « Maladie » 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 « k-anonymat » pour une certaine valeur de « k ».

  • 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 « Nom » et toutes les valeurs de l'attribut « Religion » 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 « 19 » de l'attribut « Age » peut être remplacée par « ≤ 20 », la valeur « 23 » par « 20 < Age ≤ 30 », etc.

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 « Âge », « Sexe » et « État du domicile » : 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 « k » enregistrements pour un ensemble de données k-anonymes[6].

Critiques[modifier | modifier le code]

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[7],[8] Kenig et Tassa ont présenté un algorithme d'approximation pratique qui permet de résoudre le problème de « k »-anonymisation avec une garantie d'approximation de l'ordre de [9].

Attaques[modifier | modifier le code]

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 :

  • « Attaque d'homogénéité » : cette attaque exploite le cas où toutes les valeurs d'une donnée sensible sont identiques dans un ensemble de « k » enregistrements. Dans ce cas, même si les données ont été « k »-anonymisées, la valeur sensible peut être prédite avec précision pour l'ensemble de « k » enregistrements.
  • « Attaque basée sur des informations complémentaires » : 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.
  • « Attaque par déclassement » : 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[10].

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[11].

On a également démontré que la « k »-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[12]. 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[13].

Articles connexes[modifier | modifier le code]

Notes et références[modifier | modifier le code]

  1. ↑ (en) Samarati et Sweeney, « Protecting privacy when disclosing information: k-anonymity and its enforcement through generalization and suppression » [PDF], Harvard Data Privacy Lab, (consulté le ).
  2. ↑ (en) Tore Dalenius, « Finding a Needle In a Haystack », Journal of Official Statistics, vol. 2, no 3,‎ , p. 326-336 (lire en ligne [PDF]).
  3. ↑ (en) Samarati, « Protecting Respondents' Identities in Microdata Release », IEEE Transactions on Knowledge and Data Engineering, vol. 13, no 6,‎ , p. 1010–1027 (DOI 10.1109/69.971193, lire en ligne [PDF]).
  4. ↑ (en) Sweeney, « Database Security: k-anonymity » (consulté le )
  5. ↑ (en) Sweeney, « k-anonymity: a model for protecting privacy », International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems, vol. 10, no 5,‎ , p. 557–570 (DOI 10.1142/S0218488502001648, lire en ligne).
  6. ↑ (en) Narayanan et Shmatikov, « Robust De-anonymization of Large Sparse Datasets » [PDF].
  7. ↑ (en) Roberto J. Bayardo et Rakesh Agrawal, « Data Privacy through Optimal k-anonymization », ICDE '05 Proceedings of the 21st International Conference on Data Engineering,‎ , Data de-identification reconciles the demand for release of data for research purposes and the demand for privacy from individuals. This paper proposes and evaluates an optimization algorithm for the powerful de-identification procedure known as k-anonymization. A k-anonymized dataset has the property that each record is indistinguishable from at least k - 1 others. Even simple restrictions of optimized k-anonymity are NP-hard, leading to significant computational challenges. We present a new approach to exploring the space of possible anonymizations that tames the combinatorics of the problem, and develop data-management strategies to reduce reliance on expensive operations such as sorting. Through experiments on real census data, we show the resulting algorithm can find optimal k-anonymizations under two representative cost measures and a wide range of k. We also show that the algorithm can produce good anonymizations in circumstances where the input data or input parameters preclude finding an optimal solution in reasonable time. Finally, we use the algorithm to explore the effects of different coding approaches and problem variations on anonymization quality and performance. To our knowledge, this is the first result demonstrating optimal k-anonymization of a nontrivial dataset under a general model of the problem. (ISBN 978-0-7695-2285-2, ISSN 1084-4627, DOI 10.1109/ICDE.2005.42, S2CID 17044848, lire en ligne).
  8. ↑ (en) Adam Meyerson et Ryan Williams, « On the Complexity of Optimal K-Anonymity », PODS '04 Proceedings of the Twenty-Third ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, New York, NY, ACM,‎ , p. 223–228 (ISBN 978-1581138580, DOI 10.1145/1055558.1055591, S2CID 6798963, lire en ligne [PDF])
  9. ↑ (en) Kenig et Tassa, « A practical approximation algorithm for optimal k-anonymity », Data Mining and Knowledge Discovery, vol. 25,‎ , p. 134–168 (DOI 10.1007/s10618-011-0235-9, S2CID 14158546).
  10. ↑ (en) « Attacks on Deidentificaiton's Data, Aloni Cohen, USENIX Security 2022, Distinguished Paper Award Winner ».
  11. ↑ Charu C. Aggarwal « On k-Anonymity and the Curse of Dimensionality » ()
    — « (ibid.) », dans VLDB '05 – Proceedings of the 31st International Conference on Very large Data Bases, Trondheim, Norway (ISBN 1-59593-154-6)    .
  12. ↑ (en) Angiuli, Joe Blitzstein et Jim Waldo, « How to De-Identify Your Data », ACM Queue, ACM.
  13. ↑ (en) Angiuli et Jim Waldo, « Statistical Tradeoffs between Generalization and Suppression in the De-Identification of Large-Scale Data Sets », IEEE Computer Society Intl Conference on Computers, Software, and Applications,‎ , p. 589–593 (ISBN 978-1-4673-8845-0, DOI 10.1109/COMPSAC.2016.198, S2CID 17716908).
Ce document provient de « https://fr.wikipedia.org/w/index.php?title=K-anonymisation&oldid=208971594 ».