Optimisation de l'utilité des données lors d'un processus de k-anonymisation

So that providing privacy guarantees to anonymized databases, anonymization models have emerged few decades ago. Among them, you can find k-anonymity, l-diversity, t-proximity or differential confidentiality. In this thesis, we mainly focused on the k-anonymity model through an in-depth analysis of the ways to produce databases that meet these confidentiality criteria while optimizing data utility. From a table, you can consider the set of its k-anonymous versions, which can be of exponential cardinality according to k. In a vacuum, these k-anonymous versions can be scored thanks to the amount of data modification that is correlated to the data utility. Thus, this work proposes a study of how to optimize the data utility during the process of k-anonymizing a database.First, we studied information loss metrics to estimate the amount of information lost in a table during a k-anonymization process. The metrics were used within a k-anonymization algorithm to guide equivalence class mergers leading to the production of a k-anonymous table. We tried to identify from this study characteristics in the definitions of information loss metrics allowing the production of good quality k-anonymous tables with regard to several criteria.Second, we were interested in the distribution of sensitive data into k-anonymous tables by using l-diversity and t- proximity models. More specifically, we proposed optimization strategies combining information loss metrics, l-diversity and t-proximity to be used during a k-anonymization process. The aim was then to preserv good levels of l-diversity and t-proximity of the k-anonymous tables produced, and this without sacrificing the data utility.Third, we tackled the question of the formulation of the problem of k-anonymization of a table. We relied on the original notion of generalization groups, to state the problem of k-anonymization of a table according to the incidence matrix of its associated hypergraph. Thanks to this new representation, we proposed an original procedure, declined to five algorithms, allowing to build a k-anonymous table by partitioning the equivalence classes of a k’-anonymous table with k′ >= k. Experiments carried out on two public tables have shown that the proposed algorithms outperfom the k-anonymization algorithm used previously in terms of information preservationPour donner des garanties de protection de la vie privée aux bases de données anonymisées, des modèles d'anonymisation ont vu le jour ces dernières décennies. Parmi ceux-ci, on peut citer la k-anonymité, la l-diversité, la t-proximité ou encore la confidentialité différentielle. Dans cette thèse, je me suis intéressée au modèle de k-anonymité à travers une analyse approfondie des manières de produire des bases remplissant ces critères de confidentialité tout en optimisant l'utilité des données. Partant d'une base de données, on peut en effet construire plusieurs versions k-anonymes de cette base. Certaines de ces versions k-anonymes comportent moins de modifications des données que les autres et maintiennent ainsi une meilleure utilité des données lors de leur publication. Mes travaux proposent une étude de l'optimisation de l'utilité des données lors du processus de k-anonymisation d'une base. Dans un premier temps, j'ai étudié des métriques de perte d'information permettant d'estimer la quantité d'information perdue dans une table lors d'un processus de k-anonymisation. Les métriques ont été utilisées dans un algorithme de k-anonymisation pour guider les fusions de classes d'équivalence menant à la production d'une table k-anonyme. J'ai tâché de dégager de cette étude des caractéristiques dans les définitions des métriques de perte d'information permettant de produire des tables k-anonymes de bonne qualité au regard de plusieurs critères. Dans un second temps, je me suis intéressée à la répartition des données sensibles dans les tables k-anonymes grâce aux modèles de l-diversité et de t-proximité. Plus précisément, j'ai proposé des stratégies d'optimisation mêlant métrique de perte d'information, l-diversité et t-proximité à utiliser dans un algorithme de k-anonymisation. L'objectif a été de maintenir de bons niveaux de l-diversité et de t-proximité dans les tables k-anonymes produites sans sacrifier l'utilité des données. Dans un troisième temps, je suis revenue sur la formulation du problème de k-anonymisation d'une table. Je me suis appuyée sur une nouvelle notion, les groupes de généralisation, pour énoncer le problème de k-anonymisation d'une table en fonction de la matrice d'incidence d'un hypergraphe. Grâce à cette nouvelle représentation, j'ai proposé une procédure ainsi que cinq algorithmes permettant de construire une table k-anonyme par partitionnement des classes d'équivalence d'une table k'-anonyme avec k'>= k. Des expérimentations menées sur deux tables publiques ont montré que les algorithmes proposés surpassent les performances de l'algorithme de k-anonymisation utilisé précédemment en termes de préservation d'informatio