In multi-hop wireless network (MWN), the mobile nodes relay others’ packets for enabling new applications and enhancing the network deployment and performance. However, the selfish nodes drop the packets because packet relay consumes their resources without benefits, and the malicious nodes drop the packets to launch Denial-of-Service attacks. Packet drop attacks adversely degrade the network fairness and performance in terms of throughput, delay, and packet delivery ratio. Moreover, due to the nature of wireless transmission and multi-hop packet relay, the attackers can analyze the network traffic in undetectable way to learn the users’ locations in number of hops and their communication activities causing a serious threat to the users’ privacy. In this thesis, we propose efficient security protocols for thwarting packet drop attacks and preserving users’ privacy in multi-hop wireless networks. First, we design a fair and efficient cooperation incentive protocol to stimulate the selfish nodes to relay others’ packets. The source and the destination nodes pay credits (or micropayment) to the intermediate nodes for relaying their packets. In addition to cooperation stimulation, the incentive protocol enforces fairness by rewarding credits to compensate the nodes for the consumed resources in relaying others’ packets. The protocol also discourages launching Resource-Exhaustion attacks by sending bogus packets to exhaust the intermediate nodes’ resources because the nodes pay for relaying their packets. For fair charging policy, both the source and the destination nodes are charged when the two nodes benefit from the communication. Since micropayment protocols have been originally proposed for web-based applications, we propose a practical payment model specifically designed for MWNs to consider the significant differences between web-based applications and cooperation stimulation. Although the non-repudiation property of the public-key cryptography is essential for securing the incentive protocol, the public-key cryptography requires too complicated computations and has a long signature tag. For efficient implementation, we use the public-key cryptography only for the first packet in a series and use the efficient hashing operations for the next packets, so that the overhead of the packet series converges to that of the hashing operations. Since a trusted party is not involved in the communication sessions, the nodes usually submit undeniable digital receipts (proofs of packet relay) to a centralized trusted party for updating their credit accounts. Instead of submitting large-size payment receipts, the nodes submit brief reports containing the alleged charges and rewards and store undeniable security evidences. The payment of the fair reports can be cleared with almost no processing overhead. For the cheating reports, the evidences are requested to identify and evict the cheating nodes. Since the cheating actions are exceptional, the proposed protocol can significantly reduce the required bandwidth and energy for submitting the payment data and clear the payment with almost no processing overhead while achieving the same security strength as the receipt-based protocols. Second, the payment reports are processed to extract financial information to reward the cooperative nodes, and contextual information such as the broken links to build up a trust system to measure the nodes’ packet-relay success ratios in terms of trust values. A node’s trust value is degraded whenever it does not relay a packet and improved whenever it does. A node is identified as malicious and excluded from the network once its trust value reaches to a threshold. Using trust system is necessary to keep track of the nodes’ long-term behaviors because the network packets may be dropped normally, e.g., due to mobility, or temporarily, e.g., due to network congestion, but the high frequency of packet drop is an obvious misbehavior. Then, we propose a trust-based and energy-aware routing protocol to route traffics through the highly trusted nodes having sufficient residual energy in order to establish stable routes and thus minimize the probability of route breakage. A node’s trust value is a real and live measurement to the node’s failure probability and mobility level, i.e., the low-mobility nodes having large hardware resources can perform packet relay more efficiently. In this way, the proposed protocol stimulates the nodes not only to cooperate but also to improve their packet-relay success ratio and tell the truth about their residual energy to improve their trust values and thus raise their chances to participate in future routes. Finally, we propose a privacy-preserving routing and incentive protocol for hybrid ad hoc wireless network. Micropayment is used to stimulate the nodes’ cooperation without submitting payment receipts. We only use the lightweight hashing and symmetric-key-cryptography operations to preserve the users’ privacy. The nodes’ pseudonyms are efficiently computed using hashing operations. Only trusted parties can link these pseudonyms to the real identities for charging and rewarding operations. Moreover, our protocol protects the location privacy of the anonymous source and destination nodes. Extensive analysis and simulations demonstrate that our protocols can secure the payment and trust calculation, preserve the users’ privacy with acceptable overhead, and precisely identify the malicious and the cheating nodes. Moreover, the simulation and measurement results demonstrate that our routing protocols can significantly improve route stability and thus the packet delivery ratio due to stimulating the selfish nodes’ cooperation, evicting the malicious nodes, and making informed decisions regarding route selection. In addition, the processing and submitting overheads of the payment-reports are incomparable with those of the receipts in the receipt-based incentive protocols. Our protocol also requires incomparable overhead to the signature-based protocols because the lightweight hashing operations dominate the nodes’ operations.

With the wide deployment of data intensive Internet applications and continued advances in sensing technology and biotechnology, large multidimensional datasets, possibly containing privacy-conscious information have been emerging. Mining such datasets has become increasingly common in business integration, large-scale scientific data analysis, and national security. The proposed research aims at exploring the geometric properties of the multidimensional datasets utilized in statistical learning and data mining, and providing novel techniques and frameworks for mining very large datasets while protecting the desired data privacy. The first main contribution of this research is the development of iVIBRATE interactive visualization-based approach for clustering very large datasets. The iVIBRATE framework uniquely addresses the challenges in handling irregularly shaped clusters, domain-specific cluster definition, and cluster-labeling of the data on disk. It consists of the VISTA visual cluster rendering subsystem, and the Adaptive ClusterMap Labeling subsystem. The second main contribution is the development of ``Best K Plot'(BKPlot) method for determining the critical clustering structures in multidimensional categorical data. The BKPlot method uniquely addresses two challenges in clustering categorical data: How to determine the number of clusters (the best K) and how to identify the existence of significant clustering structures. The method consists of the basic theory, the sample BKPlot theory for large datasets, and the testing method for identifying no-cluster datasets. The third main contribution of this research is the development of the theory of geometric data perturbation and its application in privacy-preserving data classification involving single party or multiparty collaboration. The key of geometric data perturbation is to find a good randomly generated rotation matrix and an appropriate noise component that provides satisfactory balance between privacy guarantee and data quality, considering possible inference attacks. When geometric perturbation is applied to collaborative multiparty data classification, it is challenging to unify the different geometric perturbations used by different parties. We study three protocols under the data-mining-service oriented framework for unifying the perturbations: 1) the threshold-satisfied voting protocol, 2) the space adaptation protocol, and 3) the space adaptation protocol with a trusted party. The tradeoffs between the privacy guarantee, the model accuracy and the cost are studied for the protocols.

Advances in data collection and data storage technologies have given way to the establishment of transactional databases among companies and organizations, as they allow enormous volumes of data to be stored efficiently. Most of the times, these vast amounts of data cannot be used as they are. A data processing should first take place, so as to extract the useful knowledge. After the useful knowledge is mined, it can be used in several ways depending on the nature of the data. Quite often, companies and organizations are willing to share data for the sake of mutual benefit. However, these benefits come with several risks, as problems with privacy might arise, as a result of this sharing. Sensitive data, along with sensitive knowledge inferred from these data, must be protected from unintentional exposure to unauthorized parties. One form of the inferred knowledge is frequent patterns, which are discovered during the process of mining the frequent itemsets from transactional databases. The problem of protecting such patterns is known as the frequent itemset hiding problem. In this thesis, we review several techniques for protecting sensitive frequent patterns in the form of frequent itemsets. After presenting a wide variety of techniques in detail, we propose a novel approach towards solving this problem. The proposed method is an approach that combines heuristics with linear-programming. We evaluate the proposed method on real datasets. For the evaluation, a number of performance metrics are presented. Finally, we compare the results of the newly proposed method with those of other state-of-the-art approaches. / Η ραγδαία εξέλιξη των τεχνολογιών συλλογής και αποθήκευσης δεδομένων οδήγησε στην καθιέρωση των βάσεων δεδομένων συναλλαγών σε οργανισμούς και εταιρείες, καθώς επιτρέπουν την αποδοτική αποθήκευση τεράστιου όγκου δεδομένων. Τις περισσότερες φορές όμως, αυτός ο τεράστιος όγκος δεδομένων δεν μπορεί να χρησιμοποιηθεί ως έχει. Μια πρώτη επεξεργασία των δεδομένων πρέπει να γίνει, ώστε να εξαχθεί η χρήσιμη πληροφορία. Ανάλογα με τη φύση των δεδομένων, αυτή η χρήσιμη πληροφορία μπορεί να χρησιμοποιηθεί στη συνέχεια αναλόγως. Αρκετά συχνά, οι εταιρείες και οι οργανισμοί είναι πρόθυμοι να μοιραστούν τα δεδομένα μεταξύ τους με στόχο το κοινό τους όφελος. Ωστόσο, αυτά τα οφέλη συνοδεύονται με διάφορους κινδύνους, καθώς ενδέχεται να προκύψουν προβλήματα ιδιωτικής φύσης, ως αποτέλεσμα αυτής της κοινής χρήσης των δεδομένων. Ευαίσθητα δεδομένα, μαζί με την ευαίσθητη γνώση που μπορεί να προκύψει από αυτά, πρέπει να προστατευτούν από την ακούσια έκθεση σε μη εξουσιοδοτημένους τρίτους. Μια μορφή της εξαχθείσας γνώσης είναι τα συχνά μοτίβα, που ανακαλύφθηκαν κατά την εξόρυξη συχνών στοιχειοσυνόλων από βάσεις δεδομένων συναλλαγών. Το πρόβλημα της προστασίας συχνών μοτίβων τέτοιας μορφής είναι γνωστό ως το πρόβλημα απόκρυψης συχνών στοιχειοσυνόλων. Στην παρούσα διπλωματική εργασία, εξετάζουμε διάφορες τεχνικές για την προστασία ευαίσθητων συχνών μοτίβων, υπό τη μορφή συχνών στοιχειοσυνόλων. Αφού παρουσιάσουμε λεπτομερώς μια ευρεία ποικιλία τεχνικών απόκρυψης, προτείνουμε μια νέα προσέγγιση για την επίλυση αυτού του προβλήματος. Η προτεινόμενη μέθοδος είναι μια προσέγγιση που συνδυάζει ευρετικές μεθόδους με γραμμικό προγραμματισμό. Για την αξιολόγηση της προτεινόμενης μεθόδου χρησιμοποιούμε πραγματικά δεδομένα. Για τον σκοπό αυτό, παρουσιάζουμε επίσης και μια σειρά από μετρικές αξιολόγησης. Τέλος, συγκρίνουμε τα αποτελέσματα της νέας προτεινόμενης μεθόδου με άλλες κορυφαίες προσεγγίσεις.

Data are valuable assets to any organizations or individuals. Data are sources of useful information which is a big part of decision making. All sectors have potential to benefit from having information. Commerce, health, and research are some of the fields that have benefited from data. On the other hand, the availability of the data makes it easy for anyone to exploit the data, which in many cases are private confidential data. It is necessary to preserve the confidentiality of the data. We study two categories of privacy: Data Value Hiding and Data Pattern Hiding. Privacy is a huge concern but equally important is the concern of data utility. Data should avoid privacy breach yet be usable. Although these two objectives are contradictory and achieving both at the same time is challenging, having knowledge of the purpose and the manner in which it will be utilized helps. In this research, we focus on some particular situations for clustering and classification problems and strive to balance the utility and privacy of the data. In the first part of this dissertation, we propose Nonnegative Matrix Factorization (NMF) based techniques that accommodate constraints defined explicitly into the update rules. These constraints determine how the factorization takes place leading to the favorable results. These methods are designed to make alterations on the matrices such that user-specified cluster properties are introduced. These methods can be used to preserve data value as well as data pattern. As NMF and K-means are proven to be equivalent, NMF is an ideal choice for pattern hiding for clustering problems. In addition to the NMF based methods, we propose methods that take into account the data structures and the attribute properties for the classification problems. We separate the work into two different parts: linear classifiers and nonlinear classifiers. We propose two different solutions based on the classifiers. We study the effect of distortion on the utility of data. We propose three distortion measurement metrics which demonstrate better characteristics than the traditional metrics. The effectiveness of the measures is examined on different benchmark datasets. The result shows that the methods have the desirable properties such as invariance to translation, rotation, and scaling.

In multi-hop wireless network (MWN), the mobile nodes relay others’ packets for enabling new applications and enhancing the network deployment and performance. However, the selfish nodes drop the packets because packet relay consumes their resources without benefits, and the malicious nodes drop the packets to launch Denial-of-Service attacks. Packet drop attacks adversely degrade the network fairness and performance in terms of throughput, delay, and packet delivery ratio. Moreover, due to the nature of wireless transmission and multi-hop packet relay, the attackers can analyze the network traffic in undetectable way to learn the users’ locations in number of hops and their communication activities causing a serious threat to the users’ privacy. In this thesis, we propose efficient security protocols for thwarting packet drop attacks and preserving users’ privacy in multi-hop wireless networks. First, we design a fair and efficient cooperation incentive protocol to stimulate the selfish nodes to relay others’ packets. The source and the destination nodes pay credits (or micropayment) to the intermediate nodes for relaying their packets. In addition to cooperation stimulation, the incentive protocol enforces fairness by rewarding credits to compensate the nodes for the consumed resources in relaying others’ packets. The protocol also discourages launching Resource-Exhaustion attacks by sending bogus packets to exhaust the intermediate nodes’ resources because the nodes pay for relaying their packets. For fair charging policy, both the source and the destination nodes are charged when the two nodes benefit from the communication. Since micropayment protocols have been originally proposed for web-based applications, we propose a practical payment model specifically designed for MWNs to consider the significant differences between web-based applications and cooperation stimulation. Although the non-repudiation property of the public-key cryptography is essential for securing the incentive protocol, the public-key cryptography requires too complicated computations and has a long signature tag. For efficient implementation, we use the public-key cryptography only for the first packet in a series and use the efficient hashing operations for the next packets, so that the overhead of the packet series converges to that of the hashing operations. Since a trusted party is not involved in the communication sessions, the nodes usually submit undeniable digital receipts (proofs of packet relay) to a centralized trusted party for updating their credit accounts. Instead of submitting large-size payment receipts, the nodes submit brief reports containing the alleged charges and rewards and store undeniable security evidences. The payment of the fair reports can be cleared with almost no processing overhead. For the cheating reports, the evidences are requested to identify and evict the cheating nodes. Since the cheating actions are exceptional, the proposed protocol can significantly reduce the required bandwidth and energy for submitting the payment data and clear the payment with almost no processing overhead while achieving the same security strength as the receipt-based protocols. Second, the payment reports are processed to extract financial information to reward the cooperative nodes, and contextual information such as the broken links to build up a trust system to measure the nodes’ packet-relay success ratios in terms of trust values. A node’s trust value is degraded whenever it does not relay a packet and improved whenever it does. A node is identified as malicious and excluded from the network once its trust value reaches to a threshold. Using trust system is necessary to keep track of the nodes’ long-term behaviors because the network packets may be dropped normally, e.g., due to mobility, or temporarily, e.g., due to network congestion, but the high frequency of packet drop is an obvious misbehavior. Then, we propose a trust-based and energy-aware routing protocol to route traffics through the highly trusted nodes having sufficient residual energy in order to establish stable routes and thus minimize the probability of route breakage. A node’s trust value is a real and live measurement to the node’s failure probability and mobility level, i.e., the low-mobility nodes having large hardware resources can perform packet relay more efficiently. In this way, the proposed protocol stimulates the nodes not only to cooperate but also to improve their packet-relay success ratio and tell the truth about their residual energy to improve their trust values and thus raise their chances to participate in future routes. Finally, we propose a privacy-preserving routing and incentive protocol for hybrid ad hoc wireless network. Micropayment is used to stimulate the nodes’ cooperation without submitting payment receipts. We only use the lightweight hashing and symmetric-key-cryptography operations to preserve the users’ privacy. The nodes’ pseudonyms are efficiently computed using hashing operations. Only trusted parties can link these pseudonyms to the real identities for charging and rewarding operations. Moreover, our protocol protects the location privacy of the anonymous source and destination nodes. Extensive analysis and simulations demonstrate that our protocols can secure the payment and trust calculation, preserve the users’ privacy with acceptable overhead, and precisely identify the malicious and the cheating nodes. Moreover, the simulation and measurement results demonstrate that our routing protocols can significantly improve route stability and thus the packet delivery ratio due to stimulating the selfish nodes’ cooperation, evicting the malicious nodes, and making informed decisions regarding route selection. In addition, the processing and submitting overheads of the payment-reports are incomparable with those of the receipts in the receipt-based incentive protocols. Our protocol also requires incomparable overhead to the signature-based protocols because the lightweight hashing operations dominate the nodes’ operations.

This work focuses on cryptographic protocol with privacy protection. The work solves the question of the elliptic curves and use in cryptography in conjunction with authentication protocols. The outputs of the work are two applications. The first application serves as a user and will replace the ID card. The second application is authentication and serves as a user authentication terminal. Both applications are designed for the Android operating system. Applications are used to select user attributes, confirm registration, user verification and show the result of verification.

La migration de données entre des sources aux schémas hétérogènes est un domaine en pleine croissance avec l'augmentation de la quantité de données en accès libre, et le regroupement des données à des fins d'apprentissage automatisé et de fouilles. Cependant, la description du processus de transformation des données d'une instance source vers une instance définie sur un schéma différent est un processus complexe même pour un utilisateur expert dans ce domaine. Cette thèse aborde le problème de la définition de mapping par un utilisateur non expert dans le domaine de la migration de données, ainsi que la vérification du respect par ce mapping des contraintes d'accès ayant été définies sur les données sources. Pour cela, dans un premier temps nous proposons un système dans lequel l'utilisateur fournit un ensemble de petits exemples de ses données, et est amené à répondre à des questions booléennes simples afin de générer un mapping correspondant à ses besoins. Dans un second temps, nous proposons un système permettant de réécrire le mapping produit de manière à assurer qu'il respecte un ensemble de vues de contrôle d'accès définis sur le schéma source du mapping. Plus précisément, le premier grand axe de cette thèse est la formalisation du problème de la définition interactive de mappings, ainsi que la description d'un cadre formel pour la résolution de celui-ci. Cette approche formelle pour la résolution du problème de définition interactive de mappings est accompagnée de preuves de bonnes propriétés. A la suite de cela, basés sur le cadre formel défini précédemment, nous proposons des algorithmes permettant de résoudre efficacement ce problème en pratique. Ces algorithmes visent à réduire le nombre de questions auxquelles l'utilisateur doit répondre afin d'obtenir un mapping correspondant à ces besoins. Pour cela, les mappings possibles sont ordonnés dans des structures de treillis imbriqués, afin de permettre un élagage efficace de l'espace des mappings à explorer. Nous proposons également une extension de cette approche à l'utilisation de contraintes d'intégrité afin d'améliorer l’efficacité de l'élagage. Le second axe majeur vise à proposer un processus de réécriture de mapping qui, étant donné un ensemble de vues de contrôle d'accès de référence, permet d'assurer que le mapping réécrit ne laisse l'accès à aucune information n'étant pas accessible via les vues de contrôle d'accès. Pour cela, nous définissons un protocole de contrôle d'accès permettant de visualiser les informations accessibles ou non à travers un ensemble de vues de contrôle d'accès. Ensuite, nous décrivons un ensemble d'algorithmes permettant la réécriture d'un mapping en un mapping sûr vis-à-vis d'un ensemble de vues de contrôle d'accès. Comme précédemment, cette approche est complétée de preuves de bonnes propriétés. Afin de réduire le nombre d'interactions nécessaires avec l'utilisateur lors de la réécriture d'un mapping, une approche permettant l'apprentissage des préférences de l'utilisateur est proposée, cela afin de permettre le choix entre un processus interactif ou automatique. L'ensemble des algorithmes décrit dans cette thèse ont fait l'objet d'un prototypage et les expériences réalisées sur ceux-ci sont présentées dans cette thèse / Data exchange between sources over heterogeneous schemas is an ever-growing field of study with the increased availability of data, oftentimes available in open access, and the pooling of such data for data mining or learning purposes. However, the description of the data exchange process from a source to a target instance defined over a different schema is a cumbersome task, even for users acquainted with data exchange. In this thesis, we address the problem of allowing a non-expert user to spec- ify a source-to-target mapping, and the problem of ensuring that the specified mapping does not leak information forbidden by the security policies defined over the source. To do so, we first provide an interactive process in which users provide small examples of their data, and answer simple boolean questions in order to specify their intended mapping. Then, we provide another process to rewrite this mapping in order to ensure its safety with respect to the source policy views. As such, the first main contribution of this thesis is to provide a formal definition of the problem of interactive mapping specification, as well as a formal resolution process for which desirable properties are proved. Then, based on this formal resolution process, practical algorithms are provided. The approach behind these algorithms aims at reducing the number of boolean questions users have to answers by making use of quasi-lattice structures to order the set of possible mappings to explore, allowing an efficient pruning of the space of explored mappings. In order to improve this pruning, an extension of this approach to the use of integrity constraints is also provided. The second main contribution is a repairing process allowing to ensure that a mapping is “safe” with respect to a set of policy views defined on its source schema, i.e., that it does not leak sensitive information. A privacy-preservation protocol is provided to visualize the information leaks of a mapping, as well as a process to rewrite an input mapping into a safe one with respect to a set of policy views. As in the first contribution, this process comes with proofs of desirable properties. In order to reduce the number of interactions needed with the user, the interactive part of the repairing process is also enriched with the possibility of learning which rewriting is preferred by users, in order to obtain a completely automatic process. Last but not least, we present extensive experiments over the open source prototypes built from two contributions of this thesis

Aujourd'hui, les progrès dans le développement d'appareils mobiles et des capteurs embarqués ont permis un essor sans précédent de services à l'utilisateur. Dans le même temps, la plupart des appareils mobiles génèrent, enregistrent et de communiquent une grande quantité de données personnelles de manière continue. La gestion sécurisée des données personnelles dans les appareils mobiles reste un défi aujourd’hui, que ce soit vis-à-vis des contraintes inhérentes à ces appareils, ou par rapport à l’accès et au partage sûrs et sécurisés de ces informations. Cette thèse adresse ces défis et se focalise sur les traces de localisation. En particulier, s’appuyant sur un serveur de données relationnel embarqué dans des appareils mobiles sécurisés, cette thèse offre une extension de ce serveur à la gestion des données spatio-temporelles (types et operateurs). Et surtout, elle propose une méthode d'indexation spatio-temporelle (TRIFL) efficace et adaptée au modèle de stockage en mémoire flash. Par ailleurs, afin de protéger les traces de localisation personnelles de l'utilisateur, une architecture distribuée et un protocole de collecte participative préservant les données de localisation ont été proposés dans PAMPAS. Cette architecture se base sur des dispositifs hautement sécurisés pour le calcul distribué des agrégats spatio-temporels sur les données privées collectées. / Nowadays, the advances in the development of mobile devices, as well as embedded sensors have permitted an unprecedented number of services to the user. At the same time, most mobile devices generate, store and communicate a large amount of personal information continuously. While managing personal information on the mobile devices is still a big challenge, sharing and accessing these information in a safe and secure way is always an open and hot topic. Personal mobile devices may have various form factors such as mobile phones, smart devices, stick computers, secure tokens or etc. It could be used to record, sense, store data of user's context or environment surrounding him. The most common contextual information is user's location. Personal data generated and stored on these devices is valuable for many applications or services to user, but it is sensitive and needs to be protected in order to ensure the individual privacy. In particular, most mobile applications have access to accurate and real-time location information, raising serious privacy concerns for their users.In this dissertation, we dedicate the two parts to manage the location traces, i.e. the spatio-temporal data on mobile devices. In particular, we offer an extension of spatio-temporal data types and operators for embedded environments. These data types reconcile the features of spatio-temporal data with the embedded requirements by offering an optimal data presentation called Spatio-temporal object (STOB) dedicated for embedded devices. More importantly, in order to optimize the query processing, we also propose an efficient indexing technique for spatio-temporal data called TRIFL designed for flash storage. TRIFL stands for TRajectory Index for Flash memory. It exploits unique properties of trajectory insertion, and optimizes the data structure for the behavior of flash and the buffer cache. These ideas allow TRIFL to archive much better performance in both Flash and magnetic storage compared to its competitors.Additionally, we also investigate the protect user's sensitive information in the remaining part of this thesis by offering a privacy-aware protocol for participatory sensing applications called PAMPAS. PAMPAS relies on secure hardware solutions and proposes a user-centric privacy-aware protocol that fully protects personal data while taking advantage of distributed computing. For this to be done, we also propose a partitioning algorithm an aggregate algorithm in PAMPAS. This combination drastically reduces the overall costs making it possible to run the protocol in near real-time at a large scale of participants, without any personal information leakage.

Dans les applications de traitement du langage naturel (NLP), la formation d’un modèle efficace nécessite souvent une quantité massive de données. Cependant, les données textuelles dans le monde réel sont dispersées dans différentes institutions ou appareils d’utilisateurs. Leur partage direct avec le fournisseur de services NLP entraîne d’énormes risques pour la confidentialité, car les données textuelles contiennent souvent des informations sensibles, entraînant une fuite potentielle de la confidentialité. Un moyen typique de protéger la confidentialité consiste à privatiser directement le texte brut et à tirer parti de la confidentialité différentielle (DP) pour protéger le texte à un niveau de protection de la confidentialité quantifiable. Par ailleurs, la protection des résultats de calcul intermédiaires via un mécanisme de privatisation de texte aléatoire est une autre solution disponible. Cependant, les mécanismes existants de privatisation des textes ne permettent pas d’obtenir un bon compromis entre confidentialité et utilité en raison de la difficulté intrinsèque de la protection de la confidentialité des textes. Leurs limitations incluent principalement les aspects suivants: (1) ces mécanismes qui privatisent le texte en appliquant la notion de dχ-privacy ne sont pas applicables à toutes les métriques de similarité en raison des exigences strictes; (2) ils privatisent chaque jeton (mot) dans le texte de manière égale en fournissant le même ensemble de sorties excessivement grand, ce qui entraîne une surprotection; (3) les méthodes actuelles ne peuvent garantir la confidentialité que pour une seule étape d’entraînement/ d’inférence en raison du manque de composition DP et de techniques d’amplification DP. Le manque du compromis utilité-confidentialité empêche l’adoption des mécanismes actuels de privatisation du texte dans les applications du monde réel. Dans ce mémoire, nous proposons deux méthodes à partir de perspectives différentes pour les étapes d’apprentissage et d’inférence tout en ne requérant aucune confiance de sécurité au serveur. La première approche est un mécanisme de privatisation de texte privé différentiel personnalisé (CusText) qui attribue à chaque jeton d’entrée un ensemble de sortie personnalisé pour fournir une protection de confidentialité adaptative plus avancée au niveau du jeton. Il surmonte également la limitation des métriques de similarité causée par la notion de dχ-privacy, en adaptant le mécanisme pour satisfaire ϵ-DP. En outre, nous proposons deux nouvelles stratégies de 5 privatisation de texte pour renforcer l’utilité du texte privatisé sans compromettre la confidentialité. La deuxième approche est un modèle Gaussien privé différentiel local (GauDP) qui réduit considérablement le volume de bruit calibrée sur la base d’un cadre avancé de comptabilité de confidentialité et améliore ainsi la précision du modèle en incorporant plusieurs composants. Le modèle se compose d’une couche LDP, d’algorithmes d’amplification DP de sous-échantillonnage et de sur-échantillonnage pour l’apprentissage et l’inférence, et d’algorithmes de composition DP pour l’étalonnage du bruit. Cette nouvelle solution garantit pour la première fois la confidentialité de l’ensemble des données d’entraînement/d’inférence. Pour évaluer nos mécanismes de privatisation de texte proposés, nous menons des expériences étendues sur plusieurs ensembles de données de différents types. Les résultats expérimentaux démontrent que nos mécanismes proposés peuvent atteindre un meilleur compromis confidentialité-utilité et une meilleure valeur d’application pratique que les méthodes existantes. En outre, nous menons également une série d’études d’analyse pour explorer les facteurs cruciaux de chaque composant qui pourront fournir plus d’informations sur la protection des textes et généraliser d’autres explorations pour la NLP préservant la confidentialité. / In Natural Language Processing (NLP) applications, training an effective model often requires a massive amount of data. However, text data in the real world are scattered in different institutions or user devices. Directly sharing them with the NLP service provider brings huge privacy risks, as text data often contains sensitive information, leading to potential privacy leakage. A typical way to protect privacy is to directly privatize raw text and leverage Differential Privacy (DP) to protect the text at a quantifiable privacy protection level. Besides, protecting the intermediate computation results via a randomized text privatization mechanism is another available solution. However, existing text privatization mechanisms fail to achieve a good privacy-utility trade-off due to the intrinsic difficulty of text privacy protection. The limitations of them mainly include the following aspects: (1) those mechanisms that privatize text by applying dχ-privacy notion are not applicable for all similarity metrics because of the strict requirements; (2) they privatize each token in the text equally by providing the same and excessively large output set which results in over-protection; (3) current methods can only guarantee privacy for either the training/inference step, but not both, because of the lack of DP composition and DP amplification techniques. Bad utility-privacy trade-off performance impedes the adoption of current text privatization mechanisms in real-world applications. In this thesis, we propose two methods from different perspectives for both training and inference stages while requiring no server security trust. The first approach is a Customized differentially private Text privatization mechanism (CusText) that assigns each input token a customized output set to provide more advanced adaptive privacy protection at the token-level. It also overcomes the limitation for the similarity metrics caused by dχ-privacy notion, by turning the mechanism to satisfy ϵ-DP. Furthermore, we provide two new text privatization strategies to boost the utility of privatized text without compromising privacy. The second approach is a Gaussian-based local Differentially Private (GauDP) model that significantly reduces calibrated noise power adding to the intermediate text representations based on an advanced privacy accounting framework and thus improves model accuracy by incorporating several components. The model consists of an LDP-layer, sub-sampling and up-sampling DP amplification algorithms 7 for training and inference, and DP composition algorithms for noise calibration. This novel solution guarantees privacy for both training and inference data. To evaluate our proposed text privatization mechanisms, we conduct extensive experiments on several datasets of different types. The experimental results demonstrate that our proposed mechanisms can achieve a better privacy-utility trade-off and better practical application value than the existing methods. In addition, we also carry out a series of analyses to explore the crucial factors for each component which will be able to provide more insights in text protection and generalize further explorations for privacy-preserving NLP.

We review our recent work on how to compute optimal repairs, optimal compliant anonymizations, and optimal safe anonymizations of ABoxes containing possibly anonymized individuals. The results can be used both to remove erroneous consequences from a knowledge base and to hide secret information before publication of the knowledge base, while keeping as much as possible of the original information. / Updated on August 27, 2021. This is an extended version of an article accepted at DL 2021.