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 ${\displaystyle 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.

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 :

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

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 ${\displaystyle \log k}$^[9].

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

• Confidentialité différentielle

• Portail de la sécurité de l’information