La confidentialité des données est un problème majeur qui doit être considéré avant de rendre publiques les données ou avant de les transmettre à des partenaires tiers avec comme but d'analyser ou de calculer des statistiques sur ces données. Leur confidentialité est principalement préservée en utilisant des techniques d'anonymisation. Dans ce contexte, un nombre important de techniques d'anonymisation a été proposé dans la littérature. Cependant, des méthodes génériques capables de s'adapter à des situations variées sont souhaitables. Nous adressons le problème de la confidentialité des données représentées sous forme de graphe, données qui nécessitent, pour différentes raisons, d'être rendues publiques. Nous considérons que l'anonymiseur n'a pas accès aux méthodes utilisées pour analyser les données. Une méthodologie générique est proposée basée sur des techniques d'apprentissage artificiel afin d'obtenir directement une fonction d'anonymisation et d'optimiser la balance entre le risque pour la confidentialité et la perte dans l'utilité des données. La méthodologie permet d'obtenir une bonne procédure d'anonymisation pour une large catégorie d'attaques et des caractéristiques à préserver dans un ensemble de données. La méthodologie est instanciée pour des graphes simples et des graphes dynamiques avec une composante temporelle. La méthodologie a été expérimentée avec succès sur des ensembles de données provenant de Twitter, Enron ou Amazon. Les résultats sont comparés avec des méthodes de référence et il est montré que la méthodologie proposée est générique et peut s'adapter automatiquement à différents contextes d'anonymisation. / Data privacy is a major problem that has to be considered before releasing datasets to the public or even to a partner company that would compute statistics or make a deep analysis of these data. Privacy is insured by performing data anonymization as required by legislation. In this context, many different anonymization techniques have been proposed in the literature. These techniques are difficult to use in a general context where attacks can be of different types, and where measures are not known to the anonymizer. Generic methods able to adapt to different situations become desirable. We are addressing the problem of privacy related to graph data which needs, for different reasons, to be publicly made available. This corresponds to the anonymized graph data publishing problem. We are placing from the perspective of an anonymizer not having access to the methods used to analyze the data. A generic methodology is proposed based on machine learning to obtain directly an anonymization function from a set of training data so as to optimize a tradeoff between privacy risk and utility loss. The method thus allows one to get a good anonymization procedure for any kind of attacks, and any characteristic in a given set. The methodology is instantiated for simple graphs and complex timestamped graphs. A tool has been developed implementing the method and has been experimented with success on real anonymized datasets coming from Twitter, Enron or Amazon. Results are compared with baseline and it is showed that the proposed method is generic and can automatically adapt itself to different anonymization contexts.

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