Il y a une forte demande économique et citoyenne pour l’ouverture des données individuelles. Cependant, la publication de telles données représente un risque pour les individus qui y sont représentés. Cette thèse s’intéresse à la problématique de l’anonymisation de tables de données multidimensionnelles contenant des données individuelles dans un objectif de publication. On se concentrera plus particulièrement sur deux familles d’approches pour l’anonymisation: la première vise à fondre chaque individu dans un groupe d’individus, la deuxième est basée sur l’ajout d’un bruit perturbateur aux données originales. Deux nouvelles approches sont développées dans le cadre de l’anonymisation par groupe, elles consistent à agréger les données à l’aide d’une technique de coclustering puis à utiliser le modèle produit, pour générer des enregistrements synthétiques, dans le cas de la première solution. La deuxième proposition quant à elle, cherche à atteindre le formalisme du k-anonymat. Enfin, nous présentons DPCocGen un nouvel algorithme d’anonymisation respectueux de la confidentialité différentielle. Tout d'abord, un partitionnement sur les domaines est utilisé pour générer un histogramme multidimensionnel bruité, un co-clustering multidimensionnel est ensuite effectué sur l'histogramme bruité résultant en un schéma de partitionnement. Enfin, le schéma obtenu est utilisé pour partitionner les données originales de manière différentiellement privée. Des individus synthétiques peuvent alors être tirés des partitions. / There is a strong economic and civic demand for the opening of individual data. However, the publication of such data poses a risk to the individuals represented in it. This thesis focuses on the problem of anonymizing multidimensional data tables containing individual data for publishing purposes. In particular, two data anonymization approaches families will be focused on: the first aims to merge each individual into a group of individuals, the second is based on the addition of disruptive noise to the original data. Two new approaches are developed in the context of group anonymization. They aggregate the data using a co-clustering technique and then use the produced model, to generate synthetic records, in the case of the first solution. While the second proposal seeks to achieve the formalism of k-anonymity. Finally, we present a new anonymization algorithm “DPCocGen” that ensures differential privacy. First, a data-independent partitioning on the domains is used to generate a perturbed multidimensional histogram, a multidimensional co-clustering is then performed on the noisy histogram resulting in a partitioning scheme. Finally, the resulting schema is used to partition the original data in a differentially private way. Synthetic individuals can then be drawn from the partitions.

La publication de données soucieuse du respect de la vie privée est au coeur des préoccupations des organisations qui souhaitent publier leurs données. Un nombre croissant d'entreprises et d'organismes collectent et publient des données à caractère personnel pour diverses raisons (études démographiques, recherche médicale,...). Selon ces cas, celui qui publie les données fait face au dilemme suivant : comment permettre à un tiers l'analyse de ces données tout en évitant de divulguer des informations trop sensibles, relatives aux individus concernés? L'enjeu est donc la capacité à publier des jeux de données en maîtrisant ce risque de divulgation, c.a.d. de traiter l'opposition entre deux critères : d'un côté, on souhaite garantir la préservation de la confidentialité sur des données personnelles et, d'autre part, on souhaite préserver au maximum l'utilité du jeu de données pour ceux qui l'exploiteraient (notamment, des chercheurs). Dans ce travail, nous cherchons d'abord à élaborer plusieurs notions d'anonymisation des données selon plusieurs contextes. Nous montrons que les index spatiaux sont extrêmement efficaces dans le cadre de la publication de données, en raison de leur capacité à passer à l'échelle. Une évaluation empirique approfondie révèle qu'il est possible de diffuser des données de grande qualité et préservant un certain niveau de confidentialité dans les données. Il est de plus possible de traiter efficacement de très grands jeux de données en grandes dimensions et cette méthode peut être étendue à un niveau de confidentialité plus fort (differential privacy). Par ailleurs, la publication séquentielle de données (mise à jour du jeu de données) est cruciale dans un grand nombre d'applications. Nous proposons une technique menant à bien cette tâche, garantissant à la fois une forte confidentialité des données et une très bonne préservation de leur utilité.

Les données personnelles sont d’une importance avérée pour presque tous les secteurs d’activité économiques grâce à toute la connaissance qu’on peut en extraire. Pour preuve, les plus grandes entreprises du monde que sont: Google, Amazon, Facebook et Apple s’en servent principalement pour fournir de leurs services. Cependant, bien que les données personnelles soient d’une grande utilité pour l’amélioration et le développement de nouveaux services, elles peuvent aussi, de manière intentionnelle ou non, nuire à la vie privée des personnes concernées. En effet, plusieurs études font état d’attaques réalisées à partir de données d’entreprises, et ceci, bien qu’ayant été anonymisées. Il devient donc nécessaire de définir des techniques fiables, pour la protection de la vie privée des personnes tout en garantissant l’utilité de ces données pour les services. Dans cette optique, l’Europe a adopté un nouveau règlement (le Règlement Général sur la Protection des Données) (EU, 2016) qui a pour but de protéger les données personnelles des citoyens européens. Cependant, ce règlement ne concerne qu’une partie du problème puisqu’il s’intéresse uniquement à la protection de la vie privée, alors que l’objectif serait de trouver le meilleur compromis entre vie privée et utilité des données. En effet, vie privée et utilité des données sont très souvent inversement proportionnelles, c’est ainsi que plus les données garantissent la vie privée, moins il y reste d’information utile. Pour répondre à ce problème de compromis entre vie privée et utilité des données, la technique la plus utilisée est l’anonymisation des données. Dans la littérature scientifique, l’anonymisation fait référence soit aux mécanismes d’anonymisation, soit aux métriques d’anonymisation. Si les mécanismes d’anonymisation sont utiles pour anonymiser les données, les métriques d’anonymisation sont elles, nécessaires pour valider ou non si le compromis entre vie privée et utilité des données a été atteint. Cependant, les métriques existantes ont plusieurs défauts parmi lesquels, le manque de précision des mesures et la difficulté d’implémentation. De plus, les métriques existantes permettent de mesurer soit la vie privée, soit l’utilité des données, mais pas les deux simultanément; ce qui rend plus complexe l’évaluation du compromis entre vie privée et utilité des données. Dans cette thèse, nous proposons une approche nouvelle, permettant de mesurer à la fois la vie privée et l’utilité des données, dénommée Discrimination Rate (DR). Le DR est une métrique basée sur la théorie de l’information, qui est pratique et permet des mesures d’une grande finesse. Le DR mesure la capacité des attributs à raffiner un ensemble d’individus, avec des valeurs comprises entre 0 et 1; le meilleur raffinement conduisant à un DR de 1. Par exemple, un identifiant a un DR égale à 1 étant donné qu’il permet de raffiner complètement un ensemble d’individus. Grâce au DR nous évaluons de manière précise et comparons les mécanismes d’anonymisation en termes d’utilité et de vie privée (aussi bien différentes instanciations d’un même mécanisme, que différents mécanismes). De plus, grâce au DR, nous proposons des définitions formelles des identifiants encore appelés informations d’identification personnelle. Ce dernier point est reconnu comme l’un des problèmes cruciaux des textes juridiques qui traitent de la protection de la vie privée. Le DR apporte donc une réponse aussi bien aux entreprises qu’aux régulateurs, par rapport aux enjeux que soulève la protection des données personnelles / Personal data promise relevant improvements in almost every economy sectors thanks to all the knowledge that can be extracted from it. As a proof of it, some of the biggest companies in the world, Google, Amazon, Facebook and Apple (GAFA) rely on this resource for providing their services. However, although personal data can be very useful for improvement and development of services, they can also, intentionally or not, harm data respondent’s privacy. Indeed, many studies have shown how data that were intended to protect respondents’ personal data were finally used to leak private information. Therefore, it becomes necessary to provide methods for protecting respondent’s privacy while ensuring utility of data for services. For this purpose, Europe has established a new regulation (The General Data Protection Regulation) (EU, 2016) that aims to protect European citizens’ personal data. However, the regulation only targets one side of the main goal as it focuses on privacy of citizens while the goal is about the best trade-off between privacy and utility. Indeed, privacy and utility are usually inversely proportional and the greater the privacy, the lower the data utility. One of the main approaches for addressing the trade-off between privacy and utility is data anonymization. In the literature, anonymization refers either to anonymization mechanisms or anonymization metrics. While the mechanisms are useful for anonymizing data, metrics are necessary to validate whether or not the best trade-off has been reached. However, existing metrics have several flaws including the lack of accuracy and the complexity of implementation. Moreover existing metrics are intended to assess either privacy or utility, this adds difficulties when assessing the trade-off between privacy and utility. In this thesis, we propose a novel approach for assessing both utility and privacy called Discrimination Rate (DR). The DR is an information theoretical approach which provides practical and fine grained measurements. The DR measures the capability of attributes to refine a set of respondents with measurements scaled between 0 and 1, the best refinement leading to single respondents. For example an identifier has a DR equals to 1 as it completely refines a set of respondents. We are therefore able to provide fine grained assessments and comparison of anonymization mechanisms (whether different instantiations of the same mechanism or different anonymization mechanisms) in terms of utility and privacy. Moreover, thanks to the DR, we provide formal definitions of identifiers (Personally Identifying Information) which has been recognized as one of the main concern of privacy regulations. The DR can therefore be used both by companies and regulators for tackling the personal data protection issues