K-anonymisation

From Wikipedia, the free encyclopedia

La k-anonymisation, ou parfois k-anonymité, 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 $k-1$ personnes dont les informations sont également publiées. Malheureusement, les garanties fournies par le k-anonymat sont ambitieuses et non mathématiques.

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

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 30 avril 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 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 $\log k$ ^[9].

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 :

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

Notes et références

↑ (en) Samarati et Sweeney, « Protecting privacy when disclosing information: k-anonymity and its enforcement through generalization and suppression » [PDF], Harvard Data Privacy Lab, 1998 (consulté le 12 avril 2017).
↑ (en) Tore Dalenius, « Finding a Needle In a Haystack », Journal of Official Statistics, vol. 2, n^o 3,‎ 1986, p. 326-336 (lire en ligne [PDF]).
↑ (en) Samarati, « Protecting Respondents' Identities in Microdata Release », IEEE Transactions on Knowledge and Data Engineering, vol. 13, n^o 6,‎ novembre 2001, p. 1010–1027 (DOI 10.1109/69.971193, lire en ligne [PDF]).
↑ (en) Sweeney, « Database Security: k-anonymity » (consulté le 19 janvier 2014)
↑ (en) Sweeney, « k-anonymity: a model for protecting privacy », International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems, vol. 10, n^o 5,‎ 2002, p. 557–570 (DOI 10.1142/S0218488502001648, lire en ligne).
↑ (en) Narayanan et Shmatikov, « Robust De-anonymization of Large Sparse Datasets » [PDF].
↑ (en) Roberto J. Bayardo et Rakesh Agrawal, « Data Privacy through Optimal k-anonymization », ICDE '05 Proceedings of the 21st International Conference on Data Engineering,‎ 2005, 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).
↑ (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,‎ 2004, p. 223–228 (ISBN 978-1581138580, DOI 10.1145/1055558.1055591, S2CID 6798963, lire en ligne [PDF])
↑ (en) Kenig et Tassa, « A practical approximation algorithm for optimal k-anonymity », Data Mining and Knowledge Discovery, vol. 25,‎ 2012, p. 134–168 (DOI 10.1007/s10618-011-0235-9, S2CID 14158546).
↑ (en) « Attacks on Deidentificaiton's Data, Aloni Cohen, USENIX Security 2022, Distinguished Paper Award Winner ».
↑ Charu C. Aggarwal « On k-Anonymity and the Curse of Dimensionality » (2005)
— « (ibid.) », dans VLDB '05 – Proceedings of the 31st International Conference on Very large Data Bases, Trondheim, Norway (ISBN 1-59593-154-6).
↑ (en) Angiuli, Joe Blitzstein et Jim Waldo, « How to De-Identify Your Data », ACM Queue, ACM.
↑ (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,‎ juin 2016, p. 589–593 (ISBN 978-1-4673-8845-0, DOI 10.1109/COMPSAC.2016.198, S2CID 17716908).

Portail de la sécurité de l’information

K-anonymisation

Critiques

Attaques

Articles connexes

Notes et références

Related Articles