Protégez les données personnelles

Je vous rappelle qu’un enregistrement, une donnée, peut être divisé en trois parties distinctes :

• le nom de la personne, qu’il va s’agir évidemment de supprimer ;

• un certain nombre d’attributs qui composent le quasi-identifiant (e.g. le code postal et l’âge) ;

• une donnée sensible (e.g. le poids de la personne).

Cette obfuscation va être atteinte en permettant à chaque nuplet de correspondre à k-DS différentes.

K-anonymat par bucketisation

Si k = 3, nous pouvons constituer 2 groupes avec des nuplets aléatoires comme vous pouvez le voir dans la figure ci-dessous : un groupe en bleu et un groupe en vert.

Ensuite, divisons ces informations en deux tables distinctes : une table "Quasi-identifiants" sur la gauche et une table "Donnée sensible" sur la droite.

Dans le tableau à gauche, les trois premières lignes correspondent au groupe 1, les 3 suivantes correspondent au groupe 2.

Trois valeurs sensibles de poids sont associées à chacun de ces groupes :

• pour le groupe 1, les trois valeurs sont respectivement 50, 70 et 90 kg ;

• pour le groupe 2, les trois valeurs sont respectivement 60, 70 et 75 kg.

De ce fait, même si on connaît le code postal et l'âge de la personne, il est impossible de connaître le poids d’une personne, avec une certitude plus grande qu'un tiers.

K-anonymat par généralisation

Afin de résoudre ce problème d’obscurité, nous allons devoir nous atteler à la réalisation de données k-anonymes par généralisation.

Ces données moins précises vont donc couvrir en même temps davantage de nuplets.

Faisons d’abord un arbre de généralisation pour chaque attribut. Si l’on prend le cas du code postal, on peut généraliser en 3 niveaux : un niveau département, un niveau région et un niveau national.

Une fois cet arbre de généralisation établi, nous allons généraliser la valeur de ces attributs jusqu'à ce que tous les nuplets soient identiques à au moins k-1 des autres.

Reprenons notre tableau de données brutes : si nous généralisons le code postal au niveau du département, les 6 nuplets restent différents.

Ce n’est donc pas encore fini ! Continuons avec la généralisation de l'âge. Comme vous pouvez le voir, nous proposons maintenant deux intervalles différents de [20-24] ou de [25-29].

Vous voyez que pour chaque individu, il y a 2 possibilités : soit il habite dans le Cher et son âge est compris entre 20 et 40 ans, soit il vient du Rhône et son âge est entre 25 et 29 ans.

L’avantage de la méthode de bucketisation

À partir de la table ci-dessus, nous allons sélectionner le code postal et le poids moyen, en regroupant par code postal :

SELECT CP, AVG(Poids)
FROM T
GROUP BY CP

Si nous prenions les données brutes, nous aurions six lignes avec le poids précis de chaque individu sur le code postal à cinq chiffres.

Sur nos données anonymisées, nous n'aurons plus que deux lignes avec la moyenne de poids des personnes du département.

Algorithme de Mondrian

Dans notre cas pratique, nous avons 2 dimensions : l'âge (ici en ordonnée) et le code postal (ici en abscisse).

La seconde étape consiste à diviser cet espace de manière récursive en groupes de points. Nous allons nous arrêter lorsque nous aurons trouvé k points distincts dans un groupe.

Le choix de l'endroit où nous allons couper les dimensions est laissé à l’implémenteur. Le principe est de découper selon la dimension qui sépare davantage les données. Ici, nous découpons une fois sur le code postal, puis nous allons découper le groupe de gauche sur l’âge et le groupe de droite sur l'âge également.

L'algorithme tire son nom du peintre du XXe siècle Piet Mondrian, pour ce tableau géométrique qui ressemble effectivement aux divisions de cet espace.

Les limites du k-anonymat

Le principal problème du k-anonymat est qu'il ne pose aucune contrainte sur les valeurs sensibles. Typiquement, si nous considérons que le poids du sixième individu est de 70 kg au lieu de 75 kg comme précédemment, nous allons nous rendre compte que toutes les personnes qui habitent dans le Rhône et qui ont un âge entre 25 et 29 ans ont le même poids.

Ainsi, même si nous ne savons pas à quelle ligne exacte correspond l'individu, nous sommes capables de déduire son poids de manière très certaine. Heureusement, le concept de l-diversité va résoudre ce problème !

Voici un exemple de base de données anonyme qui vérifie à la fois le k-anonymat et la l-diversité. Ce que nous constatons, c'est que nous avons effectivement un meilleur anonymat ! Malheureusement, cela génère inévitablement une perte de précision.

Dans la figure ci-dessus, nous n’avons plus qu'une seule classe : en posant des requêtes, on ne serait plus au niveau de la commune, ni même au niveau du département, mais au niveau national. L’intervalle d’âge est aussi plus large ici.

Venons-en maintenant au concept de differential privacy. Il permet de caractériser la sécurité d'un algorithme d'anonymisation. Ce concept s'applique donc aux algorithmes aléatoires, qui ne sont pas déterministes comme ceux que nous venons de voir. Ce type d’algorithme va tirer au sort et échantillonner certains individus pour constituer une base de données anonyme.

Un tel algorithme satisfait la contrainte d’ε-differential privacy si :

• pour toute paire de tables (donc de bases de données), D1 et D2 ne diffèrent que par la présence ou non d'un individu ;

• pour tout résultat Ω de l’algorithme, il existe ε tel que :

Voici un exemple d'algorithme de l'α, β. Cet algorithme est proposé par Rastogi et ses co-auteurs et vérifie ce critère d’ε-differential privacy.

En haut à gauche, se trouve le jeu de données initial. À l'intérieur de ce jeu, nous allons échantillonner des n-nuplets qui sont vrais avec une certaine probabilité, ici de 0,5 (soit la valeur de α+β). Nous échantillonnons ici 2 n-nuplets (on aurait pu choisir un nombre différent de n-nuplets).

Nous allons générer aussi des n-nuplets qui sont peut-être faux et qui vont être générés dans l'ensemble des nuplets possibles. Ici, nous avons 20 codes postaux différents, 10 âges différents et 4 maladies différentes.

Au final, nous arrivons à une base de données anonyme, qui va être l'union des enregistrements vrais qui ont été échantillonnés, et des faux qui ont été générés. C’est la base de données que l’on peut rendre publique !

Les avantages de la méthode differential privacy

L'intérêt de cette méthode est que, lorsqu'on calcule un certain nombre de requêtes, l'ensemble des n-nuplets générés à l'intérieur du domaine vont en quelque sorte s'annuler. Ils vont avoir une moyenne qui est à peu près nulle.

Si on échantillonne tel ou tel n-nuplet à partir du dataset véritable, cela va en fait nous donner le résultat correct ! Plus exactement, cela nous donne le résultat estimé à l'aide d'une fonction statistique. Pour mieux comprendre, nous allons compter le nombre de valeurs dans la base de données que l'on observe.

Par exemple, nous allons compter le nombre de personnes qui ont un rhume : il y en a 2. Nous allons retirer l'ensemble des personnes qui sont issues statistiquement du tirage au sort, c’est-à-dire cette probabilité β × le nombre de n-uplet qui ont un rhume dans le domaine.

Ensuite, nous allons diviser ce nombre de valeurs par α pour nous donner une estimation du nombre d'individus qui avaient véritablement un rhume dans la base de données initiale.

Ici, le calcul donne la bonne valeur, mais naturellement il faut prendre en compte une part d’erreur lorsque vous faites des estimations de ce type.

Cette méthode est bien sûr particulièrement utile si vous avez à compter le nombre d’individus qui ont telle ou telle valeur sensible.

Pour conclure ce chapitre, je vous rappelle que nous avons fait ici l’hypothèse selon laquelle cet algorithme d'anonymisation est exécuté par un éditeur qui est un tiers de confiance. Nous considérions que le résultat de cet algorithme allait être envoyé ensuite à des exploitants en qui nous n’avions pas confiance.

Mais est-ce qu'il est raisonnable d'avoir confiance en cet éditeur, c’est-à-dire la personne qui va lancer le calcul ? Eh bien, si jamais ce n'est pas le cas, il va falloir mettre en place des mécanismes plus complexes, comme le calcul sécurisé multipartite. Cela relève de la cryptographie, et c’est donc relativement difficile.

Une autre approche serait d’utiliser des matériels sécurisés, comme les cartes à puces. Dans ce cas, il faudra se reposer sur l’algorithmique, c'est-à-dire qu’il faudra être capable de construire des algorithmes qui vont tourner sur ces dispositifs sécurisés, mais à la puissance de calcul relativement faible.