Dissertationen zum Thema „Chiffrement homomorphe (informatique)“

Dans notre vie de tous les jours, nous produisons une multitude de données à chaque fois que nous accédons à un service en ligne. Certaines sont partagées volontairement et d'autres à contrecœur. Ces données sont collectées et analysées en clair, ce qui menace la vie privée de l'utilisateur et empêche la collaboration entre entités travaillant sur des données sensibles. Le chiffrement complètement homomorphe (Fully Homomorphic Encryption) apporte une lueur d'espoir en permettant d'effectuer des calculs sur des données chiffrées ce qui permet de les analyser et de les exploiter sans jamais y accéder en clair. Cette thèse se focalise sur TFHE, un récent schéma complètement homomorphe capable de réaliser un bootstrapping en un temps record. Dans celle-ci, nous introduisons une méthode d'optimisation pour sélectionner les degrés de liberté inhérents aux calculs homomorphiques permettant aux profanes d'utiliser TFHE. Nous détaillons une multitude de nouveaux algorithmes homomorphes qui améliorent l'efficacité de TFHE et réduisent voire éliminent les restrictions d'algorithmes connus. Une implémentation efficace de ceux-ci est d'ores et déjà en accès libre
In our everyday life, we leave a trail of data whenever we access online services. Some are given voluntarily and others reluctantly. Those data are collected and analyzed in the clear which leads to major threats on the user's privacy and prevents collaborations between entities working on sensitive data. In this context, Fully Homomorphic Encryption brings a new hope by enabling computation over encrypted data, which removes the need to access data in the clear to analyze and exploit it. This thesis focuses on TFHE, a recent fully homomorphic encryption scheme able to compute a bootstrapping in record time. We introduce an optimization framework to set the degrees of freedom inherent to homomorphic computations which gives non-experts the ability to use it (more) easily. We describe a plethora of new FHE algorithms which improve significantly the state of the art and limit, (if not remove) existing restrictions. Efficient open source implementations are already accessible

Le retrait d’information privé que nous nommons PIR, désigne un groupe de protocoles qui s’inscrit dans un ensemble plus vaste des technologies d’amélioration de la vie privée. Sa fonctionnalité principale est de dissimuler l’index d’un élément d’une liste accédée par un client au regard de son hôte. Sans négliger l’appart de leurs auteurs à la communauté scientifique, l’utilisabilité de ce groupe de protocoles semble limitée, car pour un client, télécharger l’intégralité de la liste est plus efficient. À ce jour, les PIR, se fondent sur des serveurs répliqués mutuellement méfiants, des périphériques de confiance ou bien des systèmes cryptographiques. Nous considérerons ici les retraits d’informations privés computationnels et plus particulièrement ceux reposant sur les réseaux euclidiens qui n’offrent des propriétés particulières, comme l’homomorphisme. Afin d’en démontrer l’utilisabilité, nous proposons un retrait d’information privé reposant sur un système cryptographique homomorphe performant et aisé d’utilisation
Private information retrieval, named PIR, is a set of protocols that is a part of privacy enhancement technologies.Its major feature is to hide the index of a record that a user retrieved from the host.Without neglecting the scientific contributions of its authors, the usability of this protocol seems hard since that, for a user, it seems more and more efficient to receive all the records.Thus far, PIR can be achieved using mutually distrustful databases replicated databases, trusted hardware, or cryptographic systems.We focus on computational private information retrieval, and specifically on thus based on cryptographic systems.This decision is contingent to the spread of cryptographic systems based on lattices who provide specific properties.To demonstrate it usability, we offer an efficient and easy-to-use private Information retrieval based on homomorphic encryption

L'annonce de l'essor du chiffrement des données se heurte à celle de l'avènement du "big data". Il n'est maintenant plus suffisant d'envoyer et de recevoir des données, il faut pouvoir les analyser, les exploiter ou encore les partager à grande échelle. Or, les données à protéger sont de plus en plus nombreuses, notamment avec la prise de conscience de l'impact qu'ont les nouvelles technologies (smartphones, internet of things, cloud,...) sur la vie privée des utilisateurs. En rendant ces données inaccessibles, le chiffrement bloque a priori les fonctionnalités auxquelles les utilisateurs et les fournisseurs de service sont habitués. Pour rétablir ces fonctionnalités, il est nécessaire de savoir calculer des fonctions de données chiffrées, et cette thèse explore plusieurs pistes dans ce sens. Dans une première partie, nous nous intéressons au chiffrement totalement homomorphe qui permet de réaliser des calculs arbitraires sur les données chiffrées. Ce type de chiffrement est cependant particulièrement coûteux, notamment à cause de l'appel souvent nécessaire à une procédure très coûteuse : le réamorçage. Nous prouvons ici que minimiser le nombre de réamorçages est un problème NP-complet et donnons une méthode pratique pour approximer ce minimum. Dans une seconde partie, nous étudions des schémas dédiés à une fonctionnalité donnée. Le premier cas d'usage considéré est celui de la déduplication vérifiable de données chiffrées. Il s'agit pour un serveur de stockage externe d'être assuré qu'il ne conserve qu'un seul exemplaire de chaque fichier, même si ceux-ci sont chiffrés, ce qui lui permet d'optimiser l'usage de ses ressources mémoires. Ensuite, nous proposons un schéma de chiffrement cherchable permettant de détecter des intrusions dans un réseau de télécommunications chiffrés. En effet, le travail d'inspection du réseau par des moteurs d'analyse est actuellement entravé par la croissance du trafic chiffré. Les résultats obtenus permettent ainsi d'assurer la confidentialité des échanges tout en garantissant l'absence d'intrusions malveillantes dans le trafic
Nowadays, encryption and services issued of ``big data" are at odds. Indeed, encryption is about protecting users privacy, while big data is about analyzing users data. Being increasingly concerned about security, users tend to encrypt their sensitive data that are subject to be accessed by other parties, including service providers. This hinders the execution of services requiring some kind of computation on users data, which makes users under obligation to choose between these services or their private life. We address this challenge in this thesis by following two directions.In the first part of this thesis, we study fully homomorphic encryption that makes possible to perform arbitrary computation on encrypted data. However, this kind of encryption is still inefficient, and this is due in part to the frequent execution of a costly procedure throughout evaluation, namely the bootstrapping. Thus, efficiency is inversely proportional to the number of bootstrappings needed to evaluate functions on encrypted data. In this thesis, we prove that finding such a minimum is NP-complete. In addition, we design a new method that efficiently finds a good approximation of it. In the second part, we design schemes that allow a precise functionality. The first one is verifiable deduplication on encrypted data, which allows a server to be sure that it keeps only one copy of each file uploaded, even if the files are encrypted, resulting in an optimization of the storage resources. The second one is intrusion detection over encrypted traffic. Current encryption techniques blinds intrusion detection services, putting the final user at risks. Our results permit to reconcile users' right to privacy and their need of keeping their network clear of all intrusion

L’émergence d’internet et l’amélioration des infrastructures de com- munication ont considérablement encouragé l’explosion des flux d’in- formations au niveau mondial. Cette évolution a été accompagnée par l’apparition de nouveaux besoins et de nouvelles attentes de la part des consommateurs. Communiquer avec ses proches ou ses collaborateurs, stocker des documents de travail, des fichiers mul- timédia, utiliser des services innovants traitant nos documents per- sonnels, tout cela se traduit immanquablement par le partage, avec des tiers, d’informations potentiellement sensibles. Ces tiers, s’ils ne sont pas de confiance, peuvent réutiliser à notre insu les données sensibles que l’on leur a confiées. Dans ce contexte, le chiffrement homomorphe apporte une bonne solution. Il permet de cacher aux yeux des tiers les données qu’ils sont en train de manipuler. Cependant, à l’heure actuelle, le chif- frement homomorphe reste complexe. Pour faire des opérations sur des données de quelques bits (données en clair), il est nécessaire de manipuler des opérandes sur quelques millions de bits (données chiffrées). Ainsi, une opération normalement simple devient longue en termes de temps de calcul. Dans cette étude, nous avons cherché à rendre le chiffrement ho- momorphe plus pratique en concevant un accélérateur spécifique. Nous nous sommes basés sur une approche de type co-conception logicielle/matérielle utilisant l’algorithme de Karatsuba. En particulier, notre approche est compatible avec le batching, qui permet de sto- cker plusieurs bits d’informations dans un même chiffré. Notre étude démontre que le batching peut être implémenté sans surcoût important comparé à l’approche sans batching, et permet à la fois de réduire les temps de calcul (calculs effectués en parallèle) et de réduire le rapport entre la taille des données chiffrées et des données en clair
The emergence of internet and the improvement of communica- tion infrastructures have considerably increased the information flow around the world. This development has come with the emergence of new needs and new expectations from consumers. Communicate with family or colleagues, store documents or multimedia files, using innovative services which processes our personal data, all of this im- plies sharing with third parties some potentially sensitive data. If third parties are untrusted, they can manipulate without our agreement data we share with them. In this context, homomorphic encryption can be a good solution. Ho- momorphic encryption can hide to the third parties the data they are processing. However, at this point, homomorphic encryption is still complex. To process a few bits of clear data (cleartext), one needs to manage a few million bits of encrypted data (ciphertext). Thus, a computation which is usually simple becomes very costly in terms of computation time. In this work, we have improved the practicability of homomorphic en- cryption by implementing a specific accelerator. We have followed a software/hardware co-design approach with the help of Karatsuba algorithm. In particular, our approach is compatible with batching, a technique that “packs" several messages into one ciphertext. Our work demonstrates that the batching can be implemented at no important additional cost compared to non-batching approaches, and allows both reducing computation time (operations are processed in parallel) and the ciphertext/cleartext ratio

La popularité de la cryptographie à base de réseau euclidien a considérablement augmenté ces dernières années avec la découverte de nouvelles fonctionnalités spectaculaires, telles que le chiffrement complètement homomorphe et l'obscurcissement. Il est désormais crucial de pouvoir analyser la sécurité concrète des cryptosystèmes à base de réseau, afin notamment de choisir leurs paramètres et d'évaluer leurs performances pratiques. Dans une première partie, nous présentons une analyse théorique ainsi que des améliorations concrètes de la réduction BKZ, qui est considérée comme l'algorithme de réduction de réseau le plus efficace en pratique en grande dimension. Tout d'abord, nous étudions la procédure principale de BKZ, l'énumération, et nous étendons l'analyse de l'énumération élaguée par Gama et al (Eurocrypt2010). Ensuite, nous présentons plusieurs améliorations de cette réduction en utilisant plusieurs techniques, telles que l'énumération élaguée, le pré-traitement avant énumération et la terminaison après un nombre fixé de tours. En se fondant sur de nombreuses expérimentations, nous présentons également un algorithme de simulation pour prédire la qualité de sortie de cette réduction. Ces travaux nous ont permis de réévaluer la sécurité de nombreux cryptosystèmes à base de réseau, mais aussi d'optimiser la résolution du problème du plus court vecteur dans un réseau. Dans une deuxième partie, nous présentons un nouvel algorithme pour le problème du plus grand commun diviseur approché, en utilisant un compromis temps-mémoire. Cet algorithme permet une meilleure attaque concrète contre le cryptosystème de chiffrement complètement homomorphe proposé par Coron et al (Crypto2011)
The popularity of lattice-based cryptography has significantly increased in the past few years with the discovery of new spectacular functionalities such as fully-homomorphic encryption and (indistinguishability) obfuscation. It has become crucial to be able to analyze the concrete security of lattice-based cryptosystems, in order to select their parameters and to assess their practical performances. In a first part, we present a theoretical analysis and concrete improvements to the so-called BKZ reduction, which is considered tô be the most efficient lattice reduction algorithm in practice for high dimensions. We begin by studying the main subroutine of BKZ, enumeration, and we extend the analysis of pruned enumeration by Gama, Nguyen and Regev (EUROCRYPT 2010). Next, we improve the BKZ algorithm by using several techniques, such as pruned enumeration, pre-processing and abort. And we discuss how to select BKZ parameters efficiently. Based on numerous experiments, we present a simulation algorithm to predict the output quality of BKZ reduction. This allows us to revise the security estimates of numerous lattice-based cryptosystems, and explain how to solve SVP by enumeration as efficiently as possible, based on the state-of-the-art. In a second part, we present a new algorithm for the approximate greatest common divisor problem, using a time/memory trade-off. This provides a better concrete attack on the fully-homomorphic encryption scheme proposed by Coron, Mandal, Naccache and Tibouchi (CRYPTO 2011). It also has other applications in cryptanalysis

Dans les schémas de chiffrement classique, l'objectif principal du schéma est d'assurer la confidentialité des données. Le chiffrement totalement homomorphe, une variante réalisée pour la première fois par Gentry, est un schéma de chiffrement qui permet également le calcul sur les données chiffrées, sans jamais avoir besoin de les déchiffrer. En l'utilisant, tout tiers non fiable avec le matériel de clé pertinent peut effectuer des calculs homomorphes, conduisant à de nombreuses applications où un tiers non fiable peut toujours être autorisée à calculer sur des chiffrements de données sensibles (cloud computing), ou où la confiance doit être décentralisée ( calcul multipartite).Cette thèse comporte deux contributions principales au chiffrement totalement homomorphe. Dans la première partie, on prend un FHE basé sur les nombres de Fermat et on étend le chiffrement sur des nombres à plusieurs bits. On ajoute la possibilité d'évaluer homomorphiquement des fonctions de petites tailles, et en les utilisant, on arrive à faire des additions et multiplications avec peu de bootstrappings, et qui peux servir comme composante des computations plus larges. Certains résultats plus récents sur les variables aléatoires sous-gaussiennes sont adaptés pour donner une meilleure analyse d'erreur.L'un des obstacles pour la généralisation de FHE est sa grande complexité computationelle, et des architectures optimisées pour accélérer les calculs FHE sur du matériel reconfigurable ont été proposées. La deuxième partie propose une architecture materiélle pour l'arithmetique des polynômes utilisés dans les systèmes comme FV. Elle peut être utlisée pour faire l'addition et la multiplication des polynômes anneaux, en utilisant une paire d'algorithmes NTT qui évite l'utilisation de bit reversal, et comprend les multiplications par les vecteurs de poids. Pour le côut de stocker les facteurs twiddles dans un ROM, on évite les mises à jour des twiddles, ce qui mène à un compte de cycle beaucoup plus petit
In conventional encryption schemes, the primary aim of the scheme is to ensure confidentiality of the data. Fully Homomorphic Encryption (FHE), a variant first realized by Gentry, is an encryption scheme which also allows for computation over the encrypted data, without ever needing to decrypt it. Using this, any untrusted third party with the relevant key material can perform homomorphic computations, leading to many applications where an untrusted party can still be allowed to compute over encryptions of sensitive data (cloud computing), or where the trust needs to be decentralized (multi-party computation).This thesis consists of two main contributions to Fully Homomorphic Encryption. In the first part, we take an FHE based on Fermat numbers and extend it to work with multi-bit numbers. We also add the ability to homomorphically evaluate small functions, with which we can compute additions and multiplication with only a few bootstrappings, and these can be used as building blocks for larger computations. Some newer results on sub-Gaussian random variables are adapted to give a better error analysis.One of the obstacles in bringing FHE to the mainstream remains its large computational complexity, and optimized architectures to accelerate FHE computations on reconfigurable hardware have been proposed. The second part of our thesis proposes an architecture for the polynomial arithmetic used in FV-like cryptosystems. This can be used to compute the sum and product of ring polynomials, using a pair of NTT algorithms which avoids the use of bit reversal, and subsumes the need for multiplication by weight vectors. For the cost of storing twiddle factors in a ROM, we avoid twiddle updates leading to a much smaller cycle count

Le chiffrement complètement homomorphe est une classe de chiffrement permettant de calculer n’importe quelle fonction sur des données chiffrées et de produire une version chiffrée du résultat. Il permet de déléguer des données à un cloud de façon sécurisée, faire effectuer des calculs, tout en gardant le caractère privé de ces données. Cependant, l’innéficacité actuelle des schémas de chiffrement complètement homomorphes, et leur inadéquation au contexte de délégation de calculs, rend son usage seul insuffisant pour cette application. Ces deux problèmes peuvent être résolus, en utilisant ce chiffrement dans un cadre plus large, en le combinant avec un schéma de chiffrement symétrique. Cette combinaison donne naissance au chiffrement complètement homomorphe hybride, conçu dans le but d’une délégation de calculs efficace, garantissant des notions de sécurité et de vie privée. Dans cette thèse, nous étudions le chiffrement complètement homomorphe hybride et ses composantes, à travers la conception de primitives cryptographiques symétriques rendant efficace cette construction hybride. En examinant les schémas de chiffrement complètement homomorphes, nous developpons des outils pour utiliser efficacement leurs propriétés homomorphiques dans un cadre plus complexe. En analysant différents schémas symétriques, et leurs composantes, nous déterminons de bons candidats pour le contexte hybride. En étudiant la sécurité des constructions optimisant l’évaluation homomorphique, nous contribuons au domaine des fonctions booléennes utilisées en cryptologie. Plus particulièrement, nous introduisons une nouvelle famille de schémas de chiffrement symétriques, avec une nouvelle construction, adaptée au contexte hybride. Ensuite, nous nous intéressons à son comportement homomorphique, et nous étudions la sécurité de cette construction. Finalement, les particularités de cette famille de schémas de chiffrement motivant des cryptanalyses spécifiques, nous développons et analysons de nouveaux critères cryptographiques booléens
Fully homomorphic encryption, firstly built in 2009, is a very powerful kind of encryption, allowing to compute any function on encrypted data, and to get an encrypted version of the result. Such encryption enables to securely delegate data to a cloud, ask for computations, recover the result, while keeping private the data during the whole process. However, today’s inefficiency of fully homomorphic encryption, and its inadequateness to the outsourcing computation context, makes its use alone insufficient for this application. Both of these issues can be circumvented, using fully homomorphic encryption in a larger framework, by combining it with a symmetric encryption scheme. This combination gives a hybrid fully homomorphic framework, designed towards efficient outsourcing computation, providing both security and privacy. In this thesis, we contribute to the study of hybridfully homomorphic framework, through the analysis, and the design of symmetric primitives making efficient this hybrid construction. Through the examination of fully homomorphic encryption schemes, we develop tools to efficiently use the homomorphic properties in a more complex framework. By investigating various symmetric encryption schemes, and buildingblocks up to the circuit level, we determine good candidates for a hybrid context. Through evaluating the security of constructions optimizing the homomorphic evaluation, we contribute to a wide study within the cryptographic Boolean functions area. More particularly, we introduce a new family of symmetric encryption schemes, with a new design, adapted to the hybrid fully homomorphic framework. We then investigate its behavior relatively to homomorphic evaluation, and we address the security of such design. Finally, particularities of this family of ciphers motivate specific cryptanalyses, therefore we develop and analyze new cryptographic Boolean criteria

Le chiffrement homomorphe est une branche de la cryptologie, dans laquelle les schémas de chiffrement offrent la possibilité de faire des calculs sur les messages chiffrés, sans besoin de les déchiffrer. L’intérêt pratique de ces schémas est dû à l’énorme quantité d'applications pour lesquels ils peuvent être utilisés. En sont un exemple le vote électronique, les calculs sur des données sensibles, comme des données médicales ou financières, le cloud computing, etc..Le premier schéma de chiffrement (complètement) homomorphe n'a été proposé qu'en 2009 par Gentry. Il a introduit une technique appelée bootstrapping, utilisée pour réduire le bruit des chiffrés : en effet, dans tous les schémas de chiffrement homomorphe proposés, les chiffrés contiennent une petite quantité de bruit, nécessaire pour des raisons de sécurité. Quand on fait des calculs sur les chiffrés bruités, le bruit augmente et, après avoir évalué un certain nombre d’opérations, ce bruit devient trop grand et, s'il n'est pas contrôlé, risque de compromettre le résultat des calculs.Le bootstrapping est du coup fondamental pour la construction des schémas de chiffrement homomorphes, mais est une technique très coûteuse, qu'il s'agisse de la mémoire nécessaire ou du temps de calcul. Les travaux qui on suivi la publication de Gentry ont eu comme objectif celui de proposer de nouveaux schémas et d’améliorer le bootstrapping pour rendre le chiffrement homomorphe faisable en pratique. L’une des constructions les plus célèbres est GSW, proposé par Gentry, Sahai et Waters en 2013. La sécurité du schéma GSW se fonde sur le problème LWE (learning with errors), considéré comme difficile en pratique. Le bootstrapping le plus rapide, exécuté sur un schéma de type GSW, a été proposé en 2015 par Ducas et Micciancio. Dans cette thèse on propose une nouvelle variante du schéma de chiffrement homomorphe de Ducas et Micciancio, appelée TFHE.Le schéma TFHE améliore les résultats précédents, en proposant un bootstrapping plus rapide (de l'ordre de quelques millisecondes) et des clés de bootstrapping plus petites, pour un même niveau de sécurité. TFHE utilise des chiffrés de type TLWE et TGSW (scalaire et ring) : l’accélération du bootstrapping est principalement due à l’utilisation d’un produit externe entre TLWE et TGSW, contrairement au produit externe GSW utilisé dans la majorité des constructions précédentes.Deux types de bootstrapping sont présentés. Le premier, appelé gate bootstrapping, est exécuté après l’évaluation homomorphique d’une porte logique (binaire ou Mux) ; le deuxième, appelé circuit bootstrapping, peut être exécuté après l’évaluation d’un nombre d'opérations homomorphiques plus grand, pour rafraîchir le résultat ou pour le rendre compatible avec la suite des calculs.Dans cette thèse on propose aussi de nouvelles techniques pour accélérer l’évaluation des calculs homomorphiques, sans bootstrapping, et des techniques de packing des données. En particulier, on présente un packing, appelé vertical packing, qui peut être utilisé pour évaluer efficacement des look-up table, on propose une évaluation via automates déterministes pondérés, et on présente un compteur homomorphe appelé TBSR qui peut être utilisé pour évaluer des fonctions arithmétiques.Pendant les travaux de thèse, le schéma TFHE a été implémenté et il est disponible en open source.La thèse contient aussi des travaux annexes. Le premier travail concerne l’étude d’un premier modèle théorique de vote électronique post-quantique basé sur le chiffrement homomorphe, le deuxième analyse la sécurité des familles de chiffrement homomorphe dans le cas d'une utilisation pratique sur le cloud, et le troisième ouvre sur une solution différente pour le calcul sécurisé, le calcul multi-partite
Fully homomorphic encryption is a new branch of cryptology, allowing to perform computations on encrypted data, without having to decrypt them. The main interest of homomorphic encryption schemes is the large number of practical applications for which they can be used. Examples are given by electronic voting, computations on sensitive data, such as medical or financial data, cloud computing, etc..The first fully homomorphic encryption scheme has been proposed in 2009 by Gentry. He introduced a new technique, called bootstrapping, used to reduce the noise in ciphertexts: in fact, in all the proposed homomorphic encryption schemes, the ciphertexts contain a small amount of noise, which is necessary for security reasons. If we perform computations on noisy ciphertexts, the noise increases and, after a certain number of operations, the noise becomes to large and it could compromise the correctness of the final result, if not controlled.Bootstrapping is then fundamental to construct fully homomorphic encryption schemes, but it is very costly in terms of both memory and time consuming.After Gentry’s breakthrough, the presented schemes had the goal to propose new constructions and to improve bootstrapping, in order to make homomorphic encryption practical. One of the most known schemes is GSW, proposed by Gentry, Sahai et Waters in 2013. The security of GSW is based on the LWE (learning with errors) problem, which is considered hard in practice. The most rapid bootstrapping on a GSW-based scheme has been presented by Ducas and Micciancio in 2015. In this thesis, we propose a new variant of the scheme proposed by Ducas and Micciancio, that we call TFHE.The TFHE scheme improves previous results, by performing a faster bootstrapping (in the range of a few milliseconds) and by using smaller bootstrapping keys, for the same security level. TFHE uses TLWE and TGSW ciphertexts (both scalar and ring): the acceleration of bootstrapping is mainly due to the replacement of the internal GSW product, used in the majority of previous constructions, with an external product between TLWE and TGSW.Two kinds of bootstrapping are presented. The first one, called gate bootstrapping, is performed after the evaluation of a homomorphic gate (binary or Mux); the second one, called circuit bootstrapping, can be executed after the evaluation of a larger number of homomorphic operations, in order to refresh the result or to make it compatible with the following computations.In this thesis, we also propose new techniques to improve homomorphic computations without bootstrapping and new packing techniques. In particular, we present a vertical packing, that can be used to efficiently evaluate look-up tables, we propose an evaluation via weighted deterministic automata, and we present a homomorphic counter, called TBSR, that can be used to evaluate arithmetic functions.During the thesis, the TFHE scheme has been implemented and it is available in open source.The thesis contains also ancillary works. The first one concerns the study of the first model of post-quantum electronic voting based on fully homomorphic encryption, the second one analyzes the security of homomorphic encryption in a practical cloud implementation scenario, and the third one opens up about a different solution for secure computing, multi-party computation

Craig Gentry a proposé en 2009 le premier schéma de chiffrement complétement homomorphe. Depuis, un effort conséquent a été, et est toujours, fourni par la communauté scientifique pour rendre utilisable ce nouveau type de cryptographie. Son côté révolutionnaire tient au fait qu'il permet d'effectuer des traitements directement sur des données chiffrées (sans que l’entité réalisant les traitements ait besoin de les déchiffrer). Plusieurs pistes se sont développées en parallèle, explorant d'un côté des schémas complétement homomorphes, plus flexibles entermes d'applications mais plus contraignants en termes de taille de données ou en coût de calcul, et de l'autre côté des schémas quelque peu homomorphes, moins flexibles mais aussi moins coûteux. Cette thèse, réalisée au sein de la chaire de cyberdéfense des systèmes navals, s’inscrit dans cette dynamique. Nous avons endossé divers rôles. Tout d’abord un rôle d'attaquant pour éprouver la sécurité des hypothèses sous-jacentes aux propositions. Ensuite, nous avons effectué un état de l’art comparatif des schémas quelque peu homomorphes les plus prometteurs afin d'identifier le(s) meilleur(s) selon les cas d’usages, et de donner des conseils dans le choix des paramètres influant sur leur niveau de sécurité, la taille des données chiffrées et le coût algorithmique des calculs. Enfin, nous avons endossé le rôle du concepteur en proposant un nouveau schéma complétement homomorphe performant, ainsi que son implémentation mise à disposition sur github
Craig Gentry presented in 2009 the first fully homomorphic encryption scheme. Since then, a tremendous effort has been, and still is, dedicated by the cryptographic community to make practical this new kind of cryptography. It is revolutionnary because it enables direct computation on encrypted data (without the need for the computing entity to decrypt them). Several trends have been developed in parallel, exploring on one side fully homomorphic encryption schemes, more versatile for applications but more costly in terms of time and memory. On the other side, the somewhat homomorphic encryption schemes are less flexible but more efficient. This thesis, achieved within the Chair of Naval Cyber Defence, contributes to these trends. We have endorsed different roles. First, an attacker position to assess the hardness of the security assumptions of the proposals. Then, we conducted a state-of-the-art of the most promising schemes in order to identify the best(s) depending on the use-cases and to give precise advice to appropriately set the parameters that drive security level, ciphertext sizes and computation costs. Last, we endorsed a designer role. We proposed a new powerful fully homomorphic encryption scheme together with its open-source implementation, available on github

Cette thèse est réalisée dans le cadre du projet BPI DeepTech, en collaboration avec la société Fair&Smart, veillant principalement à la protection des données personnelles conformément au Règlement Général sur la Protection des Données (RGPD). Dans ce contexte, nous avons proposé un modèle neuronal profond pour l'extraction d'informations dans les documents administratifs semi-structurés (DSSs). En raison du manque de données d'entraînement publiques, nous avons proposé un générateur artificiel de DSSs qui peut générer plusieurs classes de documents avec une large variation de contenu et de mise en page. Les documents sont générés à l'aide de variables aléatoires permettant de gérer le contenu et la mise en page en respectant des contraintes visant à garantir leur proximité avec des documents réels. Des métriques ont été introduites pour évaluer la diversité des DSSs générés en termes de contenu et de mise en page. Les résultats de l'évaluation ont montré que les jeux de données générés pour trois types de DSSs (fiches de paie, tickets de caisse et factures) présentent un degré élevé de diversité, ce qui permet d'éviter le sur-apprentissage lors de l'entraînement des systèmes d'extraction d'informations. En s'appuyant sur le format spécifique des DSSs, constitué de paires de mots (mots-clés, informations) situés dans des voisinages proches spatialement, le document est modélisé sous forme de graphe où les nœuds représentent les mots et les arcs, les relations de voisinage. Le graphe est incorporé dans un réseau d'attention à graphe (GAT) multi-couches (Multi-GAT). Celui-ci applique le mécanisme d'attention multi-têtes permettant d'apprendre l'importance des voisins de chaque mot pour mieux le classer. Une première version de ce modèle a été utilisée en mode supervisé et a obtenu un score F1 de 96 % sur deux jeux de données de factures et de fiches de paie générées, et de 89 % sur un ensemble de tickets de caisse réels (SROIE). Nous avons ensuite enrichi le Multi-GAT avec un plongement multimodal de l'information au niveau des mots (avec des composantes textuelle, visuelle et positionnelle), et l'avons associé à un auto-encodeur variationnel à graphe (VGAE). Ce modèle fonctionne en mode semi-supervisé, capable d'apprendre à partir des données annotées et non annotées simultanément. Pour optimiser au mieux la classification des nœuds du graphe, nous avons proposé un semi-VGAE dont l'encodeur partage ses premières couches avec le classifieur Multi-GAT. Cette optimisation est encore renforcée par la proposition d'une fonction de perte VGAE gérée par la perte de classification. En utilisant une petite base de données non annotées, nous avons pu améliorer de plus de 3 % le score F1 obtenu sur un ensemble de factures générées. Destiné à fonctionner dans un environnement protégé, nous avons adapté l'architecture du modèle pour son chiffrement homomorphe. Nous avons étudié une méthode de réduction de la dimensionnalité du modèle Multi-GAT. Ensuite, nous avons proposé une approche d'approximation polynomiale des fonctions non-linéaires dans le modèle. Pour réduire la dimension du modèle, nous avons proposé une méthode de fusion de caractéristiques multimodales qui nécessite peu de paramètres supplémentaires et qui réduit les dimensions du modèle tout en améliorant ses performances. Pour l'adaptation au chiffrement, nous avons étudié des approximations polynomiales de degrés faibles aux fonctions non-linéaires avec une utilisation des techniques de distillation de connaissance et de fine tuning pour mieux adapter le modèle aux nouvelles approximations. Nous avons pu minimiser la perte lors de l'approximation d'environ 3 % pour deux jeux de données de factures ainsi qu'un jeu de données de fiches de paie et de 5 % pour SROIE
This thesis is being carried out as part of the BPI DeepTech project, in collaboration with the company Fair&Smart, primarily looking after the protection of personal data in accordance with the General Data Protection Regulation (RGPD). In this context, we have proposed a deep neural model for extracting information in semi-structured administrative documents (SSDs). Due to the lack of public training datasets, we have proposed an artificial generator of SSDs that can generate several classes of documents with a wide variation in content and layout. Documents are generated using random variables to manage content and layout, while respecting constraints aimed at ensuring their similarity to real documents. Metrics were introduced to evaluate the content and layout diversity of the generated SSDs. The results of the evaluation have shown that the generated datasets for three SSD types (payslips, receipts and invoices) present a high diversity level, thus avoiding overfitting when training the information extraction systems. Based on the specific format of SSDs, consisting specifically of word pairs (keywords-information) located in spatially close neighborhoods, the document is modeled as a graph where nodes represent words and edges, neighborhood connections. The graph is fed into a multi-layer graph attention network (Multi-GAT). The latter applies the multi-head attention mechanism to learn the importance of each word's neighbors in order to better classify it. A first version of this model was used in supervised mode and obtained an F1 score of 96% on two generated invoice and payslip datasets, and 89% on a real receipt dataset (SROIE). We then enriched the multi-GAT with multimodal embedding of word-level information (textual, visual and positional), and combined it with a variational graph auto-encoder (VGAE). This model operates in semi-supervised mode, being able to learn on both labeled and unlabeled data simultaneously. To further optimize the graph node classification, we have proposed a semi-VGAE whose encoder shares its first layers with the multi-GAT classifier. This is also reinforced by the proposal of a VGAE loss function managed by the classification loss. Using a small unlabeled dataset, we were able to improve the F1 score obtained on a generated invoice dataset by over 3%. Intended to operate in a protected environment, we have adapted the architecture of the model to suit its homomorphic encryption. We studied a method of dimensionality reduction of the Multi-GAT model. We then proposed a polynomial approximation approach for the non-linear functions in the model. To reduce the dimensionality of the model, we proposed a multimodal feature fusion method that requires few additional parameters and reduces the dimensions of the model while improving its performance. For the encryption adaptation, we studied low-degree polynomial approximations of nonlinear functions, using knowledge distillation and fine-tuning techniques to better adapt the model to the new approximations. We were able to minimize the approximation loss by around 3% on two invoice datasets as well as one payslip dataset and by 5% on SROIE

L’apprentissage automatique (ou le Machine Learning) est un domaine scientifique très en vogue en raison de sa capacité à résoudre les problèmes automatiquement et de son large spectre d’applications (par exemple, le domaine de la finance, le domaine médical, etc.). Les techniques de Machine Learning (ML) ont attiré mon attention du point de vue cryptographique dans le sens où les travaux de ma thèse ont eu comme objectif une utilisation sécurisée des méthodes de ML. Cette thèse traite l'utilisation sécurisée des techniques de ML sous deux volets : la confidentialité des données d’apprentissage ou des données pour l’inférence et l’intégrité de l’évaluation à distance des différentes méthodes de ML. La plupart des autres travaux traitent que la confidentialité des données et que pour la phase d’inférence. Dans ma thèse, j’ai proposé trois architectures pour assurer une évaluation à distance sécurisée pour les configurations suivantes de ML: la classification à distance grâce à un réseau de neurones (NN), l’apprentissage fédéré (FL) et l’apprentissage par transfert (TL). Notamment, les architectures pour l’apprentissage fédéré et l’apprentissage par transfert sont les premiers approches qui traitent à la fois la confidentialité de données et l'intégrité du calcul. Ces architectures ont été construites en utilisant ou en modifiant un schéma de calcul vérifiable pré-existant pour des données chiffrées en homomorphe. Nos travaux ouvrent des nombreuses perspectives, qui ne concernent pas forcément que les architectures de ML, mais aussi les outils utilisés pour assurer les propriétés de sécurité. Par exemple, une perspective importante est de rajouter de la confidentialité différentielle (DP) à notre architecture d’apprentissage fédéré
Machine Learning (ML) represents a new trend in science because of its power to solve problems automatically and its wide spectrum of applications (e.g., business, healthcare domain, etc.). This attractive technology caught our attention from a cryptography point of view in the sense that we worked during this Ph.D. to ensure secure usage of ML setups. Our Ph.D. work proposes a secure remote evaluation over different ML setups (for inference and for training). This thesis addresses two cornerstones: confidentiality of training or inference data and remote evaluation integrity in different ML setups (federated learning or transfer learning-based inference). In contrast, most other works focus only on data confidentiality. In our thesis, we proposed three architectures/frameworks to ensure a secure remote evaluation for the following ML setups: Neural Networks (NN), Federated Learning (FL), and Transfer Learning (TL). Particularly, our FL and TL architectures are the first that treat both the confidentiality and integrity security properties. We built these architectures using or modifying pre-existing VC schemes over homomorphic encrypted data: mainly we use VC protocols for BFV and Paillier schemes. An essential characteristic for our architectures is their generality, in the sense, if there are improvements in VC protocols and HE schemes, our frameworks can easily take into account these new approaches. This work opens up many perspectives, not only in privacy-preserving ML architectures, but also for the tools used to ensure the security properties. For example, one important perspective is to add differential privacy (DP) to our FL architecture

Le chiffrement totalement homomorphe est un type de chiffrement qui permet de manipuler directement des données chiffrées. De cette manière, il est possible de traiter des données sensibles sans avoir à les déchiffrer au préalable, permettant ainsi de préserver la confidentialité des données traitées. À l'époque du numérique à outrance et du "cloud computing" ce genre de chiffrement a le potentiel pour impacter considérablement la protection de la vie privée. Cependant, du fait de sa découverte récente par Gentry en 2009, nous manquons encore de recul à son propos. C'est pourquoi de nombreuses incertitudes demeurent, notamment concernant sa sécurité et son efficacité en pratique, et devront être éclaircies avant une éventuelle utilisation à large échelle. Cette thèse s'inscrit dans cette problématique et se concentre sur l'amélioration des performances de ce genre de chiffrement en pratique. Pour cela nous nous sommes intéressés à l'optimisation de l'arithmétique utilisée par ces schémas, qu'elle soit sous-jacente au problème du "Ring-Learning With Errors" sur lequel la sécurité des schémas considérés est basée, ou bien spécifique aux procédures de calculs requises par certains de ces schémas. Nous considérons également l'optimisation des calculs nécessaires à certaines applications possibles du chiffrement homomorphe, et en particulier la classification de données privées, de sorte à proposer des techniques de calculs innovantes ainsi que des méthodes pour effectuer ces calculs de manière efficace. L'efficacité de nos différentes méthodes est illustrée à travers des implémentations logicielles et des comparaisons aux techniques de l'état de l'art
Fully homomorphic encryption is a kind of encryption offering the ability to manipulate encrypted data directly through their ciphertexts. In this way it is possible to process sensitive data without having to decrypt them beforehand, ensuring therefore the datas' confidentiality. At the numeric and cloud computing era this kind of encryption has the potential to considerably enhance privacy protection. However, because of its recent discovery by Gentry in 2009, we do not have enough hindsight about it yet. Therefore several uncertainties remain, in particular concerning its security and efficiency in practice, and should be clarified before an eventual widespread use. This thesis deals with this issue and focus on performance enhancement of this kind of encryption in practice. In this perspective we have been interested in the optimization of the arithmetic used by these schemes, either the arithmetic underlying the Ring Learning With Errors problem on which the security of these schemes is based on, or the arithmetic specific to the computations required by the procedures of some of these schemes. We have also considered the optimization of the computations required by some specific applications of homomorphic encryption, and in particular for the classification of private data, and we propose methods and innovative technics in order to perform these computations efficiently. We illustrate the efficiency of our different methods through different software implementations and comparisons to the related art

L'apprentissage automatique en tant que service (MLaaS) a accéléré l'adoption des techniques d'apprentissage automatique dans divers domaines. Toutefois, cette tendance a également soulevé de sérieuses inquiétudes quant à la sécurité et à la confidentialité des données sensibles utilisées dans les modèles d'apprentissage automatique. Pour relever ce défi, notre approche consiste à utiliser le chiffrement homomorphique.Cette thèse explore l'application du chiffrement homomorphe dans divers contextes d'apprentissage automatique. La première partie du travail se concentre sur l'utilisation du chiffrement homomorphe dans un environnement multi-cloud, où le chiffrement est appliqué à des opérations simples telles que l'addition et la multiplication.Cette thèse explore l'application du chiffrement homomorphique à l'algorithme k-nearest neighbors (k-NN). L'étude présente une implémentation pratique de l'algorithme k-NN utilisant le cryptage homomorphique et démontre la faisabilité de cette approche sur une variété d'ensembles de données. Les résultats montrent que les performances de l'algorithme k-NN utilisant le cryptage homomorphique sont comparables à celles de l'algorithme non chiffré.Troisièmement, les travaux étudient l'application du chiffrement homomorphique à l'algorithme de regroupement k-means. Comme pour l'étude k-NN, la thèse présente une implémentation pratique de l'algorithme k-means utilisant le chiffrement homomorphique et évalue ses performances sur différents ensembles de données.Enfin, la thèse explore la combinaison du chiffrement homomorphique avec des techniques de confidentialité différentielle (DP) pour améliorer encore la confidentialité des modèles d'apprentissage automatique. L'étude propose une nouvelle approche qui combine le chiffrement homomorphique avec la protection différentielle afin d'obtenir de meilleures garanties de confidentialité pour les modèles d'apprentissage automatique. La recherche présentée dans cette thèse contribue au corpus croissant de recherche sur l'intersection du chiffrement homomorphique et de l'apprentissage automatique, en fournissant des implémentations pratiques et des évaluations du chiffrement homomorphique dans divers contextes d'apprentissage automatique
Machine Learning as a Service (MLaaS) has accelerated the adoption of machine learning techniques in various domains. However, this trend has also raised serious concerns over the security and privacy of the sensitive data used in machine learning models. To address this challenge, our approach is to use homomorphic encryption.The aim of this thesis is to examine the implementation of homomorphic encryption in different applications of machine learning.. The first part of the work focuses on the use of homomorphic encryption in a multi-cloud environment, where the encryption is applied to simple operations such as addition and multiplication.This thesis explores the application of homomorphic encryption to the k-nearest neighbors (k-NN) algorithm. The study presents a practical implementation of the k-NN algorithm using homomorphic encryption and demonstrates the feasibility of this approach on a variety of datasets. The results show that the performance of the k-NN algorithm using homomorphic encryption is comparable to that of the unencrypted algorithm.Third, the work investigates the application of homomorphic encryption to the k-means clustering algorithm. Similar to the k-NN study, the thesis presents a practical implementation of the k-means algorithm using homomorphic encryption and evaluates its performance on various datasets.Finally, the thesis explores the combination of homomorphic encryption with differential privacy (DP) techniques to further enhance the privacy of machine learning models. The study proposes a novel approach that combines homomorphic encryption with DP to achieve better privacy guarantees for machine learning models. The research presented in this thesis contributes to the growing body of research on the intersection of homomorphic encryption and machine learning, providing practical implementations and evaluations of homomorphic encryption in various machine learning contexts.iffalseAccording to Gartner, 5.8 Billion Enterprise and Automotive IoT endpoints will be in use at the end of 2020 while Statistica shows that IoT enablers solutions (such as Cloud, analytics, security) will reach 15 Billion of euros in the European Union market by 2025. However, these IoT devices have not enough resource capacity to process the data collected by their sensors making these devices vulnerable and prone to attack. To avoid processing data within the IoT devices, the trend is to outsource the sensed data to the Cloud that has both resourceful data storage and data processing. Nevertheless, the externalized data may be sensitive, and the users may lose privacy on the data content while allowing the cloud providers to access and possibly use these data to their own business. To avoid this situation and preserve data privacy in the Cloud datacenter, one possible solution is to use the fully homomorphic encryption (FHE) that assures both confidentiality and efficiency of the processing. In many smart environments such as smart cities, smart health, smart farming, industry 4.0, etc. where massive data are generated, there is a need to apply machine learning (ML) techniques, hence contributing to the decision making to act on the smart environment. Indeed, the challenging issue in this context is to adapt the ML approaches to apply them on encrypted data so that the decision taken on encrypted data can be reported on the cleartext data. This PhD thesis is a cooperative research work between two teams ROC and MSDMA of CEDRIC Lab. It aims at exploring the use of ML and FHE in smart applications where IoT devices collect sensitive data to outsource them on untrusted Cloud datacenter for computing thanks to ML models

L'objet de cette thèse est la conception de protocoles pour l'entraînement de modèles d'apprentissage automatique avec protection des données d'entraînement. Pour ce faire, nous nous sommes concentrés sur deux outils de confidentialité, la confidentialité différentielle et le chiffrement homomorphe. Alors que la confidentialité différentielle permet de fournir un modèle fonctionnel protégé des attaques sur la confidentialité par les utilisateurs finaux, le chiffrement homomorphe permet d'utiliser un serveur comme intermédiaire totalement aveugle entre les propriétaires des données, qui fournit des ressources de calcul sans aucun accès aux informations en clair. Cependant, ces deux techniques sont de nature totalement différente et impliquent toutes deux leurs propres contraintes qui peuvent interférer : la confidentialité différentielle nécessite généralement l'utilisation d'un bruit continu et non borné, tandis que le chiffrement homomorphe ne peut traiter que des nombres encodés avec un nombre limité de bits. Les travaux présentés visent à faire fonctionner ensemble ces deux outils de confidentialité en gérant leurs interférences et même en les exploitant afin que les deux techniques puissent bénéficier l'une de l'autre.Dans notre premier travail, SPEED, nous étendons le modèle de menace du protocole PATE (Private Aggregation of Teacher Ensembles) au cas d'un serveur honnête mais curieux en protégeant les calculs du serveur par une couche homomorphe. Nous définissons soigneusement quelles opérations sont effectuées homomorphiquement pour faire le moins de calculs possible dans le domaine chiffré très coûteux tout en révélant suffisamment peu d'informations en clair pour être facilement protégé par la confidentialité différentielle. Ce compromis nous contraint à réaliser une opération argmax dans le domaine chiffré, qui, même si elle est raisonnable, reste coûteuse. C'est pourquoi nous proposons SHIELD dans une autre contribution, un opérateur argmax volontairement imprécis, à la fois pour satisfaire la confidentialité différentielle et alléger le calcul homomorphe. La dernière contribution présentée combine la confidentialité différentielle et le chiffrement homomorphe pour sécuriser un protocole d'apprentissage fédéré. Le principal défi de cette combinaison provient de la discrétisation nécessaire du bruit induit par le chiffrement, qui complique l'analyse des garanties de confidentialité différentielle et justifie la conception et l'utilisation d'un nouvel opérateur de quantification qui commute avec l'agrégation
The purpose of this PhD is to design protocols to collaboratively train machine learning models while keeping the training data private. To do so, we focused on two privacy tools, namely differential privacy and homomorphic encryption. While differential privacy enables to deliver a functional model immune to attacks on the training data privacy by end-users, homomorphic encryption allows to make use of a server as a totally blind intermediary between the data owners, that provides computational resource without any access to clear information. Yet, these two techniques are of totally different natures and both entail their own constraints that may interfere: differential privacy generally requires the use of continuous and unbounded noise whereas homomorphic encryption can only deal with numbers encoded with a quite limited number of bits. The presented contributions make these two privacy tools work together by coping with their interferences and even leveraging them so that the two techniques may benefit from each other.In our first work, SPEED, we built on Private Aggregation of Teacher Ensembles (PATE) framework and extend the threat model to deal with an honest but curious server by covering the server computations with a homomorphic layer. We carefully define which operations are realised homomorphically to make as less computation as possible in the costly encrypted domain while revealing little enough information in clear to be easily protected by differential privacy. This trade-off forced us to realise an argmax operation in the encrypted domain, which, even if reasonable, remained expensive. That is why we propose SHIELD in another contribution, an argmax operator made inaccurate on purpose, both to satisfy differential privacy and lighten the homomorphic computation. The last presented contribution combines differential privacy and homomorphic encryption to secure a federated learning protocol. The main challenge of this combination comes from the necessary quantisation of the noise induced by encryption, that complicates the differential privacy analysis and justifies the design and use of a novel quantisation operator that commutes with the aggregation

Un nombre important et en constante augmentation de systèmes numériques nous entoure. Tablettes, smartphones et objets connectés ne sont que quelques exemples apparents de ces technologies omniprésentes, dont la majeure partie est enfouie, invisible à l'utilisateur. Les microprocesseurs, au cœur de ces systèmes, sont soumis à de fortes contraintes en ressources, sûreté de fonctionnement et se doivent, plus que jamais, de proposer une sécurité renforcée. La tâche est d'autant plus complexe qu'un tel système, par sa proximité avec l'utilisateur, offre une large surface d'attaque.Cette thèse, se concentre sur une propriété essentielle attendue pour un tel système, la confidentialité, le maintien du secret du programme et des données qu'il manipule. En effet, l'analyse du programme, des instructions qui le compose, est une étape essentielle dans la conception d'une attaque. D'autre part, un programme est amené à manipuler des données sensibles (clés cryptographiques, mots de passes, ...), qui doivent rester secrètes pour ne pas compromettre la sécurité du système.Cette thèse, se concentre sur une propriété essentielle attendue pour un tel système, la confidentialité, le maintien du secret du programme et des données qu'il manipule. Une première contribution de ces travaux est une méthode de chiffrement d'un code, basée sur le graphe de flot de contrôle, rendant possible l'utilisation d'algorithmes de chiffrement par flots, légers et efficaces. Protéger les accès mémoires aux données d'un programme s'avère plus complexe. Dans cette optique, nous proposons l'utilisation d'un chiffrement homomorphe pour chiffrer les données stockées en mémoire et les maintenir sous forme chiffrée lors de l'exécution des instructions. Enfin, nous présenterons l'intégration de ces propositions dans une architecture de processeur et les résultats d'évaluation sur logique programmable (FPGA) avec plusieurs programmes d'exemples
Embedded processors are today ubiquitous, dozen of them compose and orchestrate every technology surrounding us, from tablets to smartphones and a large amount of invisible ones. At the core of these systems, processors gather data, process them and interact with the outside world. As such, they are excepted to meet very strict safety and security requirements. From a security perspective, the task is even more difficult considering the user has a physical access to the device, allowing a wide range of specifically tailored attacks.Confidentiality, in terms of both software code and data is one of the fundamental properties expected for such systems. The first contribution of this work is a software encryption method based on the control flow graph of the program. This enables the use of stream ciphers to provide lightweight and efficient encryption, suitable for constrained processors. The second contribution is a data encryption mechanism based on homomorphic encryption. With this scheme, sensible data remain encrypted not only in memory, but also during computations. Then, the integration and evaluation of these solutions on Field Programmable Gate Array (FPGA) with some example programs will be discussed

Le calcul multipartite sécurisé (en anglais, MPC) [Yao82,GMW87a] permet à des agents d'un réseau de communication de calculer conjointement une fonction de leurs entrées sans avoir à n'en rien révéler de plus que le résultat du calcul lui-même. Une question primordiale est de savoir dans quelle mesure le coût en communication entre les agents dépend de la complexité calculatoire de la fonction en question. Un point de départ est l'étude d'une hypothétique barrière de la taille du circuit. L'existence d'une telle barrière est suggérée par le fait que tous les protocoles MPC fondateurs, des années 80 et 90, emploient une approche "porte-logique-par-porte-logique" au calcul sécurisé: la communication d'un tel protocole sera nécessairement au moins linéaire en le nombre de portes, c'est-à-dire en la taille du circuit. De plus ceux-ci représentent moralement l'état de l'art encore de nos jours en ce qui concerne la sécurité dite "par théorie de l'information". La barrière de la taille du circuit a été franchie pour le MPC avec sécurité calculatoire, mais sous des hypothèses structurées impliquant l'existence de chiffrement totalement homomorphe (en anglais, FHE) [Gen09] ou de partage de secret homomorphe (en anglais, HSS) [BGI16a]. De plus, il existe des protocoles avec sécurité par théorie de l'information dont la communication en-ligne (mais pas la communication totale) est sous-linéaire en la taille du circuit [IKM + 13, DNNR17, Cou19]. Notre méthodologie de recherche consiste à s'inspirer des techniques developpées dans le modèle de l'aléa corrélée dans lequel tout résultat pourra être considéré comme plus "fondamental" que le modèle calculatoire (de par le type de sécurité obtenue) mais qui est néanmoins un modèle inadapté à comprendre la complexité de communication du MPC (puisque que l'on s'autorise à ne pas compter toute quantité de communication qui peut être reléguée à une phase "hors-ligne", c'est-à-dire avant que les participants au calcul ne prennent connaissance de leurs entrées) pour développer de nouvelles méthodes dans le modèle calculatoire. Avec cette approche, nous obtenons des protocoles franchissant la barrière de la taille du circuit sous l'hypothèse de la sécurité quasipolynomiale de LPN [CM21] ou sous l'hypothèse QR+LPN [BCM22]. Ces hypothèses calculatoires n'étant pas précédement réputées impliquer l'existence de MPC sous-linéaire, la pertinence de notre méthodologie est, dans une certaine mesure, validée a posteriori. Plus fondamentalement cependant, nos travaux empruntent un nouveau paradigme pour construire du MPC sous-linéaire, sans utiliser les outils "avec de fortes propriétés homomorphiques" que sont le FHE ou du HSS. En combinant toutes nos techniques héritées de notre étude du modèle de l'aléa corrélé, nous parvenons à briser la barrière des deux joueurs pour le calcul sécurisé avec communication sous-linéaire, sans FHE [BCM23]. Spécifiquement, nous présentons le premier protocole à plus de deux participants dont la communication est sous-linéaire en la taille du circuit et qui ne soit pas fondé sur des hypothèses sous lesquelles on sait déjà faire du FHE. Parallèlement à ces travaux centrés sur la sécurité calculatoire, nous montrons [CMPR23] comment adapter les approches à deux joueurs utilisant du HSS, à la [BGI16a], pour gurantir une sécurité "théorie de l'information" à l'un des deux joueurs et une sécurité calculatoire à l'autre. Ceci est, de façon prouvable, la notion de sécurité la plus forte que l'on puisse espérer en présence de seulement deux joueurs (sans aléa corrélé). Nous obtenons le premier protocole de ce type avec communication sous-linéaire, qui ne soit pas fondé sur des hypothèses sous lesquelles on sait déjà faire du FHE
Secure Multi-Party Computation (MPC) [Yao82, GMW87a] allows a set of mutually distrusting parties to perform some joint computation on their private inputs without having to reveal anything beyond the output. A major open question is to understand how strongly the communication complexity of MPC and the computational complexity of the function being computed are correlated. An intriguing starting point is the study of the circuit-size barrier. The relevance of this barrier is a historical, and potentially absolute, one: all seminal protocols from the 1980s and 1990s use a "gate-by-gate" approach, requiring interaction between the parties for each (multiplicative) gate of the circuit to be computed, and this remains the state of the art if we wish to provide the strongest security guarantees. The circuit-size barrier has been broken in the computational setting from specific, structured, computational assumption, via Fully Homomorphic Encryption (FHE) [Gen09] and later Homomorphic Secret Sharing [BGI16a]. Additionally, the circuit-size barrier for online communication has been broken (in the correlated randomness model) information-theoretically [IKM + 13, DNNR17, Cou19], but no such result is known for the total communication complexity (in the plain model). Our methodology is to draw inspiration from known approaches in the correlated randomness model, which we view simultaneously as fundamental (because it provides information-theoretic security guarantees) and inherently limited (because the best we can hope for in this model is to understand the online communication complexity of secure computation), in order to devise new ways to break the circuit-size barrier in the computational setting. In the absence of a better way to decide when concrete progress has been made, we take extending the set of assumptions known to imply sublinear-communication secure computation as "proof of conceptual novelty". This approach has allowed us to break the circuit-size barrier under quasipolynomial LPN [CM21] or QR and LPN [BCM22]. More fundamentally, these works constituted a paradigm shift, away from the "homomorphism-based" approaches of FHE and HSS, which ultimately allowed us to break the two-party barrier for sublinear-communication secure computation and provide in [BCM23] the first sublinear-communication protocol with more than two parties, without FHE. Orthogonally to this line of work, purely focusing on computational security, we showed in [CMPR23] that [BGI16a] could be adapted to provide information-theoretic security for one of the two parties, and computational security for the other: these are provably the strongest security guarantees one can hope to achieve in the two-party setting (without setup), and ours is the first sublinear-communication protocol in this setting which does not use FHE

L’objectif de mes travaux tout au long de cette thèse a été de permettre à des algorithmes complexes d’apprentissage machine de pouvoir être appliqués (lors de leur phase d’inférence) sur des données dont la confidentialité est préservée. Un contexte d’application est l’envoi de données sur un serveur distant sur lequel un algorithme est évalué. Selon les cas, pour des raisons éthiques, légales ou commerciales, la confidentialité des données qui sont envoyées doit pouvoir être respectée. Il est possible pour cela de désigner des autorités en lesquels tous les acteurs du protocole peuvent avoir confiance. Pourquoi accorder à des entités un tel niveau de confiance dans des cas où la confidentialité des données d’un utilisateur est essentielle ? La cryptographie offre en effet des alternatives, dont le chiffrement totalement homomorphe.Le chiffrement homomorphe permet, en théorie, l’évaluation de n’importe quelle fonction dans le domaine chiffré. Son utilisation peut donc être imaginée dans le cas ou un utilisateur envoie des données chiffrées sur un serveur distant qui détient un algorithme puissant d’apprentissage machine. La phase d’inférence de cet algorithme est alors effectuée sur donnes chiffrées et le résultat est renvoyé à l’utilisateur pour déchiffrement. La cryptographie propose d’autre méthodes de calcul sur données chiffrées qui sont présentées succinctement dans le manuscrit. Pour faire court, la particularité du chiffrement homomorphe est qu’il ne nécessite aucune interaction entre l’utilisateur et le serveur. Dans ma thèse, je présente trois principaux algorithmes d’apprentissage machine sécurisés : une évaluation sur données et modèle chiffrés d’un réseau de neurone récursif et discret, le réseau de Hopfield ; une reconnaissance de locuteur sur modèle chiffré pour un réseau autoencodeur, le système VGGVox; une évaluation sur données chiffrées d’un classifieur des k plus proches voisins (ou classifieur k-NN). Notamment, notre classifieur k-NN sécurisé est le premier tel algorithme évalué de manière totalement homomorphe. Nos travaux ouvrent de nombreuses perspectives, notamment dans le domaine de l’apprentissage collaboratif sécurisé
We aim to provide a set tools allowing for machine learning algorithms to yield their intended results while ensuring confidentiality properties are achieved for the underlying data. This can be achieved through regulatory measures such as prohibiting the use of a sensitive database in certain cases and restricting its access to certain law enforcement agencies. The fundamental reason for the existence of our work - and every other work like it - is the following: why trust that an outside entity will not misuse personal data when you can have assurances of that fact ? This applies both in the case of a private company that may use/sell your data for profit, legally or illegally. It also applies to use by a government which may or may not have the proper safeguards against abuse, as well as the proper security for data storage and access. In our case, we provide such confidentiality properties though the use of Fully Homomorphic Encryption (FHE). Precisely, most of our work focuses on finding new algorithms for secure outsourced machine learning evaluation using FHE. While other privacy and confidentiality preserving methods are touched upon briefly, we focused our research on homomorphic encryption and strive to explain our choice and its general context. We present three main novel secure machine learning applications: a confidentiality-preserving recursive discrete neural network; a model-confidential embedding-based neural network; a confidentiality-preserving k-NN classifier. Notably, our secure k-NN classifier is the only such algorithm in the literature obtaining a result noninteractively. We evaluate the accuracy and efficiency of these three applications on real-world machine learning problems. We show that our secure schemes compare very favorably to their non-secure counterparts in terms of accuracy, while still running in realistic time. Beyond these schemes themselves, this thesis promotes a specific research direction for secure machine learning. We argue for less (though still some) focus on deep convolutional neural networks and show that looking at somewhat lesser known machine learning algorithms can yield promising results

Notre approche dans cette thèse était d'identifier où le chiffrement complètement homomorphe (FHE) pouvait être utilisé pour le domaine des sciences informatiques et de construire une plate-forme expérimentale qui nous permette de tester des algorithmes de traitement de l'information manipulant des données chiffrées. La première partie de cette thèse est consacrée à l'état de l'art. Nous présentons d'abord les systèmes de chiffrement homomorphes conçus avant 2008, puis nous présentons ceux adressant la problématique du chiffrement complètement homomorphe. Nous décrivons plusieurs méthodes de chiffrement d'intérêt pour cette thèse et discutons de leurs implémentations FHE. Enfin, nous présentons des circuits de Yao car ils peuvent résoudre des problèmes similaires que le FHE et nous parlons brièvement du chiffrement fonctionnel (FE). La deuxième partie de cette thèse présente nos contributions. Nous commençons par expliquer comment le FHE peut être utile dans divers scénarios et décrivons plusieurs cas d'utilisation pratique identifiés au cours de la thèse. Ensuite, nous décrivons notre approche pour effectuer des calculs sur des données chiffrées à l'aide du FHE et expliquons comment nous avons pu développer une plate-forme pour l'exécution dans le domaine chiffré d'une large gamme d'algorithmes en s'appuyant seulement sur l'addition et la multiplication homomorphes. Nous détaillons ensuite notre solution pour effectuer des requêtes privées sur une base de données chiffrées en utilisant le chiffrement homomorphe. Dans un dernier chapitre, nous présentons nos résultats expérimentaux
Our approach in this thesis was to identify where FHE could be used in computer science and to build an experimental platform that allow us to test real-life algorithm running on homomorphically-encrypted data. The first part of this thesis is dedicated to the state of the art. We first present homomorphic encryption schemes designed before 2008 and then move to the Fully Homomorphic Encryption period. We describe several schemes of interest for this thesis and discuss FHE implementations. Finally, we present Yao’s garbled circuits as they can solve similar problems as FHE and briefly talk about Functional Encryption (FE). The second part of this thesis is for our contributions to the subject. We begin by explaining how FHE can be useful in various scenarios and try to provide practical use cases that we identified during the thesis. Then, we describe our approach to perform computations on encrypted data using FHE and explain how we were able to build on just the homomorphic addition and multiplication a platform for the execution in the encrypted domain of a wide range of algorithms. We then detail our solution for performing private queries on an encrypted database using homomorphic encryption. In a final chapter, we present our experimental results

De nos jours, le “cloud computing” permet de mutualiser et de traiter de grandes quantités de données génétiques à un coût minime et sans avoir à maintenir une infrastructure propre. Ces données sont notamment utilisées dans des études d'association pangénomiques (“Genome Wide Association Studies” ou GWAS) afin d’identifier des variants génétiques associées à certaines maladies. Cependant, leur externalisation induit de nombreux problèmes en matière de sécurité. Notamment, le génome humain représente l'unique identité biologique d’un individu et est donc par nature une information très sensible. L'objectif de ces travaux de thèse est de protéger des données génétiques lors de leur partage, stockage et traitement sur le cloud. Nous avons développé différents outils de sécurité fondés sur le tatouage, des mécanismes cryptographiques et leur combinaison. Dans un premier temps, en utilisant le chiffrement homomorphe, nous avons proposé une version originale sécurisée de l’approche GWAS fondée sur la technique dite “collapsing method” ; une technique qui s’appuie sur la régression logistique. Pour faire face aux problèmes de complexité de calcul et de mémoire liés à l’exploitation du chiffrement homomorphe, nous avons proposé un protocole qui profite de différents outils cryptographiques (PGP, fonction de hachage) pour partager entre plusieurs unités de recherche des études GWAS sur des variants rares de manière sécurisée, cela sans augmenter la complexité de calcul. En parallèle, nous avons développé une méthode de crypto-tatouage qui exploite la sécurité sémantique des schémas de chiffrement homomorphe, pour permettre à un cloud de protéger/vérifier l’intégrité de bases de données génétiques externalisées par différents utilisateurs. Ce schéma de crypto-tatouage est dynamique dans le sens où le tatouage est réactualisé au fil des mises à jour des données par leurs propriétaires sans cependant retatouer l’ensemble des jeux de données. Dans le même temps, nous avons proposé la première solution de tatouage robuste qui permet de protéger la propriété intellectuelle et le traçage de traitres pour des données génétiques utilisées dans des GWAS
Nowadays, cloud computing allows researchers and health professionals to flexibly store and process large amounts of genetic data remotely, without a need to purchase and to maintain their own infrastructures. These data are especially used in genome-wide association studies (GWAS) in order to conduct the identification of genetic variants that are associated with some diseases. However, genetic data outsourcing or sharing in the cloud induces many security issues. In addition, a human genome is very sensitive by nature and represents the unique biological identity of its owner. The objective of this thesis work is to protect genetic data during their sharing, storage and processing. We have developped new security tools that are based on watermarking and cryptographic mechanisms, as well as on the combination of them. First, we have proposed a privacy-preserving method that allows to compute the secure collapsing method based on the logistic regression model using homomorphic encryption (HE). To overcome the computational and storage overhead of HE-based solutions, we have developed a framework that allows secure performing of GWAS for rare variants without increasing complexity compared to its nonsecure version. It is based on several security mechanisms including encryption. In parallel of these works, we have exploited the semantic security of some HE schemes so as to develop a dynamic watermarking method that allows integrity control for encrypted data. At last, we have developed a robust watermarking tool for GWAS data for traitor tracing purposes

La mutualisation et l'externalisation de données concernent de nombreux domaines y compris celui de la santé. Au-delà de la réduction des coûts de maintenance, l'intérêt est d'améliorer la prise en charge des patients par le déploiement d'outils d'aide au diagnostic fondés sur la réutilisation des données. Dans un tel environnement, la sécurité des données (confidentialité, intégrité et traçabilité) est un enjeu majeur. C'est dans ce contexte que s'inscrivent ces travaux de thèse. Ils concernent en particulier la sécurisation des techniques de recherche d'images par le contenu (CBIR) et de « machine learning » qui sont au c'ur des systèmes d'aide au diagnostic. Ces techniques permettent de trouver des images semblables à une image requête non encore interprétée. L'objectif est de définir des approches capables d'exploiter des données externalisées et sécurisées, et de permettre à un « cloud » de fournir une aide au diagnostic. Plusieurs mécanismes permettent le traitement de données chiffrées, mais la plupart sont dépendants d'interactions entre différentes entités (l'utilisateur, le cloud voire un tiers de confiance) et doivent être combinés judicieusement de manière à ne pas laisser fuir d'information lors d'un traitement.Au cours de ces trois années de thèse, nous nous sommes dans un premier temps intéressés à la sécurisation à l'aide du chiffrement homomorphe, d'un système de CBIR externalisé sous la contrainte d'aucune interaction entre le fournisseur de service et l'utilisateur. Dans un second temps, nous avons développé une approche de « Machine Learning » sécurisée fondée sur le perceptron multicouches, dont la phase d'apprentissage peut être externalisée de manière sûre, l'enjeu étant d'assurer la convergence de cette dernière. L'ensemble des données et des paramètres du modèle sont chiffrés. Du fait que ces systèmes d'aides doivent exploiter des informations issues de plusieurs sources, chacune externalisant ses données chiffrées sous sa propre clef, nous nous sommes intéressés au problème du partage de données chiffrées. Un problème traité par les schémas de « Proxy Re-Encryption » (PRE). Dans ce contexte, nous avons proposé le premier schéma PRE qui permet à la fois le partage et le traitement des données chiffrées. Nous avons également travaillé sur un schéma de tatouage de données chiffrées pour tracer et vérifier l'intégrité des données dans cet environnement partagé. Le message tatoué dans le chiffré est accessible que l'image soit ou non chiffrée et offre plusieurs services de sécurité fondés sur le tatouage
Cloud computing has emerged as a successful paradigm allowing individuals and companies to store and process large amounts of data without a need to purchase and maintain their own networks and computer systems. In healthcare for example, different initiatives aim at sharing medical images and Personal Health Records (PHR) in between health professionals or hospitals with the help of the cloud. In such an environment, data security (confidentiality, integrity and traceability) is a major issue. In this context that these thesis works, it concerns in particular the securing of Content Based Image Retrieval (CBIR) techniques and machine learning (ML) which are at the heart of diagnostic decision support systems. These techniques make it possible to find similar images to an image not yet interpreted. The goal is to define approaches that can exploit secure externalized data and enable a cloud to provide a diagnostic support. Several mechanisms allow the processing of encrypted data, but most are dependent on interactions between different entities (the user, the cloud or a trusted third party) and must be combined judiciously so as to not leak information. During these three years of thesis, we initially focused on securing an outsourced CBIR system under the constraint of no interaction between the users and the service provider (cloud). In a second step, we have developed a secure machine learning approach based on multilayer perceptron (MLP), whose learning phase can be outsourced in a secure way, the challenge being to ensure the convergence of the MLP. All the data and parameters of the model are encrypted using homomorphic encryption. Because these systems need to use information from multiple sources, each of which outsources its encrypted data under its own key, we are interested in the problem of sharing encrypted data. A problem known by the "Proxy Re-Encryption" (PRE) schemes. In this context, we have proposed the first PRE scheme that allows both the sharing and the processing of encrypted data. We also worked on watermarking scheme over encrypted data in order to trace and verify the integrity of data in this shared environment. The embedded message is accessible whether or not the image is encrypted and provides several services

Traitant des données très sensibles, les systèmes de gestion d'identité doivent fournir une protection adéquate de la confidentialité. En utilisant le calcul multipartite (MPC), le chiffrement homomorphe (HE) et le chiffrement fonctionnel (FE), cette thèse aborde la conception et la mise en œuvre de systèmes biométriques préservant la confidentialité pour de multiples scénarios. Nous améliorons les travaux existants dans le domaine, en équilibrant la précision et la performance avec les garanties de sécurité. Nous allons au-delà des adversaires semi-honnêtes pour garantir la correction face aux adversaires malveillants. Enfin, nous abordons la question de la fuite des données biométriques lors de la révélation du résultat, un problème de confidentialité souvent négligé dans la littérature. Les principales contributions de cette thèse sont : - Une nouvelle solution d'identification de visage construite sur la FE pour produits scalaires atténuant la fuite d'entrée. - Un nouveau protocole de calcul à deux parties, Funshade, pour préserver la confidentialité des opérations biométriques de calcul de distance avec seuil. - Une méthode innovante d'identification biométrique préservant la confidentialité, basée sur la notion de test de groupe appelée Grote. - Un nouveau protocole de décryptage distribué avec masquage collaboratif traitant la fuite d'entrée, appelé Colmade. - Un protocole de calcul tripartite à majorité honnête, Banners, pour réaliser l'inférence malicieusement sécurisée de réseaux neuronaux binarisés. - Une bibliothèque Python HE nommée Pyfhel, offrant une abstraction de haut niveau et des fonctionnalités de bas niveau, avec des applications dans l'enseignement
Dealing with highly sensitive data, identity management systems must provide adequate privacy protection as they leverage biometrics technology. Wielding Multi-Party Computation (MPC), Homomorphic Encryption (HE) and Functional Encryption (FE), this thesis tackles the design and implementation of practical privacy-preserving biometric systems, from the feature extraction to the matching with enrolled users. This work is consecrated to the design of secure biometric solutions for multiple scenarios, putting special care to balance accuracy and performance with the security guarantees, while improving upon existing works in the domain. We go beyond privacy preservation against semi-honest adversaries by also ensuring correctness facing malicious adversaries. Lastly, we address the leakage of biometric data when revealing the output, a privacy concern often overlooked in the literature. The main contributions of this thesis are: • A new face identification solution built on FE-based private inner product matching mitigating input leakage. • A novel efficient two-party computation protocol, Funshade, to preserve the privacy of biometric thresholded distance metric operations. • An innovative method to perform privacy-preserving biometric identification based on the notion of group testing named Grote. • A new distributed decryption protocol with collaborative masking addressing input leakage, dubbed Colmade. • An honest majority three-party computation protocol, Banners, to perform maliciously secure inference of Binarized Neural Networks. • A HE Python library named Pyfhel, offering a high-level abstraction and low-level functionalities, with applications in teaching

Le chiffrement totalement homomorphe permet d’effectuer des calculs sur des données chiffrées sans fuite d’information sur celles-ci. Pour résumer, un utilisateur peut chiffrer des données, tandis qu’un serveur, qui n’a pas accès à la clé de déchiffrement, peut appliquer à l’aveugle un algorithme sur ces entrées. Le résultat final est lui aussi chiffré, et il ne peut être lu que par l’utilisateur qui possède la clé secrète. Dans cette thèse, nous présentons des nouvelles techniques et constructions pour le chiffrement totalement homomorphe qui sont motivées par des applications en apprentissage automatique, en portant une attention particulière au problème de l’inférence homomorphe, c’est-à-dire l’évaluation de modèles cognitifs déjà entrainé sur des données chiffrées. Premièrement, nous proposons un nouveau schéma de chiffrement totalement homomorphe adapté à l’évaluation de réseaux de neurones artificiels sur des données chiffrées. Notre schéma atteint une complexité qui est essentiellement indépendante du nombre de couches dans le réseau, alors que l’efficacité des schéma proposés précédemment dépend fortement de la topologie du réseau. Ensuite, nous présentons une nouvelle technique pour préserver la confidentialité du circuit pour le chiffrement totalement homomorphe. Ceci permet de cacher l’algorithme qui a été exécuté sur les données chiffrées, comme nécessaire pour protéger les modèles propriétaires d’apprentissage automatique. Notre mécanisme rajoute un coût supplémentaire très faible pour un niveau de sécurité égal. Ensemble, ces résultats renforcent les fondations du chiffrement totalement homomorphe efficace pour l’apprentissage automatique, et représentent un pas en avant vers l’apprentissage profond pratique préservant la confidentialité. Enfin, nous présentons et implémentons un protocole basé sur le chiffrement totalement homomorphe pour le problème de recherche d’information confidentielle, c’est-à-dire un scénario où un utilisateur envoie une requête à une base de donnée tenue par un serveur sans révéler cette requête
Fully homomorphic encryption enables computation on encrypted data without leaking any information about the underlying data. In short, a party can encrypt some input data, while another party, that does not have access to the decryption key, can blindly perform some computation on this encrypted input. The final result is also encrypted, and it can be recovered only by the party that possesses the secret key. In this thesis, we present new techniques/designs for FHE that are motivated by applications to machine learning, with a particular attention to the problem of homomorphic inference, i.e., the evaluation of already trained cognitive models on encrypted data. First, we propose a novel FHE scheme that is tailored to evaluating neural networks on encrypted inputs. Our scheme achieves complexity that is essentially independent of the number of layers in the network, whereas the efficiency of previously proposed schemes strongly depends on the topology of the network. Second, we present a new technique for achieving circuit privacy for FHE. This allows us to hide the computation that is performed on the encrypted data, as is necessary to protect proprietary machine learning algorithms. Our mechanism incurs very small computational overhead while keeping the same security parameters. Together, these results strengthen the foundations of efficient FHE for machine learning, and pave the way towards practical privacy-preserving deep learning. Finally, we present and implement a protocol based on homomorphic encryption for the problem of private information retrieval, i.e., the scenario where a party wants to query a database held by another party without revealing the query itself

L’avènement de l’ère digitale a changé la façon dont les individus communiquent à travers le monde, et a amené de nouvelles problématiques en terme de vie privée. La notion d’anonymat la plus répandue pour les communications sur Internet consiste à empêcher tout acteur du réseau de connaître à la fois l’expéditeur d’un message et son destinataire. Bien que ce niveau de protection soit adéquat pour l’utilisateur d’Internet moyen, il est insuffisant lorsqu’un individu peut être condamné pour le simple envoi de documents à une tierce partie. C’est le cas en particulier des lanceurs d’alerte, prenant des risques personnels pour informer le public de pratiques illégales ou antidémocratiques menées par de grandes organisations. Dans cette thèse, nous envisageons un niveau d’anonymat plus fort, où l’objectif est de dissimuler le fait même qu’un utilisateur envoie ou reçoive des données. Pour cela, nous délaissons l’architecture client-serveur couramment utilisée dans les réseaux anonymes, en faveur d’une architecture entièrement distribuée et homogène, où chaque utilisateur remplit également le rôle de serveur relai, lui permettant de dissimuler son propre trafic dans celui qu’il relai pour les autres. Dans cette optique, nous proposons un nouveau protocole pour les communications pairs à pairs sur Internet. À l’aide de récents outils de preuves cryptographiques, nous prouvons que ce protocole réalise les propriétés d’anonymat désirées. De plus, nous montrons par une étude pratique que, bien que le protocole induise une grande latence dans les communications, il assure un fort anonymat, même pour des réseaux de petite taille
With the development of online communications in the past decades, new privacy concerns have emerged. A lot of research effort have been focusing on concealing relationships in Internet communications. However, most works do not prevent particular network actors from learning the original sender or the intended receiver of a communication. While this level of privacy is satisfactory for the common citizen, it is insufficient in contexts where individuals can be convicted for the mere sending of documents to a third party. This is the case for so-called whistle-blowers, who take personal risks to alert the public of anti-democratic or illegal actions performed by large organisations. In this thesis, we consider a stronger notion of anonymity for peer-to-peer communications on the Internet, and aim at concealing the very fact that users take part in communications. To this end, we deviate from the traditional client-server architecture endorsed by most existing anonymous networks, in favor of a homogeneous, fully distributed architecture in which every user also acts as a relay server, allowing it to conceal its own traffic in the traffic it relays for others. In this setting, we design an Internet overlay inspired from previous works, that also proposes new privacy-enhancing mechanisms, such as the use of relationship pseudonyms for managing identities. We formally prove with state-of-the-art cryptographic proof frameworks that this protocol achieves our privacy goals. Furthermore, a practical study of the protocol shows that it introduces high latency in the delivery of messages, but ensures a high anonymity level even for networks of small size

La cryptographie à base de réseaux euclidiens a généré un vif intérêt durant les deux dernièresdécennies grâce à des propriétés intéressantes, incluant une conjecture de résistance àl’ordinateur quantique, de fortes garanties de sécurité provenant d’hypothèses de difficulté sur lepire cas et la construction de schémas de chiffrement pleinement homomorphes. Cela dit, bienqu’elle soit cruciale à bon nombre de schémas à base de réseaux euclidiens, la génération debruit gaussien reste peu étudiée et continue de limiter l’efficacité de cette cryptographie nouvelle.Cette thèse s’attelle dans un premier temps à améliorer l’efficacité des générateurs de bruitgaussien pour les signatures hache-puis-signe à base de réseaux euclidiens. Nous proposons unnouvel algorithme non-centré, avec un compromis temps-mémoire flexible, aussi rapide que savariante centrée pour des tables pré-calculées de tailles acceptables en pratique. Nousemployons également la divergence de Rényi afin de réduire la précision nécessaire à la doubleprécision standard. Notre second propos tient à construire Falcon, un nouveau schéma designature hache-puis-signe, basé sur la méthode théorique de Gentry, Peikert et Vaikuntanathanpour les signatures à base de réseaux euclidiens. Nous instancions cette méthode sur les réseauxNTRU avec un nouvel algorithme de génération de trappes
Lattice-based cryptography has generated considerable interest in the last two decades due toattractive features, including conjectured security against quantum attacks, strong securityguarantees from worst-case hardness assumptions and constructions of fully homomorphicencryption schemes. On the other hand, even though it is a crucial part of many lattice-basedschemes, Gaussian sampling is still lagging and continues to limit the effectiveness of this newcryptography. The first goal of this thesis is to improve the efficiency of Gaussian sampling forlattice-based hash-and-sign signature schemes. We propose a non-centered algorithm, with aflexible time-memory tradeoff, as fast as its centered variant for practicable size of precomputedtables. We also use the Rényi divergence to bound the precision requirement to the standarddouble precision. Our second objective is to construct Falcon, a new hash-and-sign signaturescheme, based on the theoretical framework of Gentry, Peikert and Vaikuntanathan for latticebasedsignatures. We instantiate that framework over NTRU lattices with a new trapdoor sampler

La cryptographie à base de réseaux euclidiens est aujourd'hui un domaine scientifique en pleine expansion et connait une évolution rapide et accélérée par l'attractivité du chiffrement complètement homomorphe ou des applications multilinéaires cryptographiques. Ses propriétés sont très attractives : une sécurité pouvant être réduite à la difficulté des pires cas de problèmes sur les réseaux euclidiens, une efficacité asymptotique quasi-optimale et une résistance présupposée aux ordinateurs quantiques. Cependant, on dénombre encore peu de résultats de recherche sur les constructions à visée pratique pour un niveau de sécurité fixé. Cette thèse s'inscrit dans cette direction et travaille à réduire l'écart entre la théorie et la pratique de la cryptographie à clé publique récente. Dans cette thèse, nous concevons et implémentons une signature numérique basée sur les réseaux euclidiens, deux schémas de chiffrement complètement homomorphe et des applications multilinéaires cryptographiques. Notre signature digitale ultra-performante, BLISS, ouvre la voie à la mise en pratique de la cryptographie à base de réseaux sur petites architectures et est un candidat sérieux à la cryptographie post-quantique. Nos schémas de chiffrement complètement homomorphes permettent d'évaluer des circuits non triviaux de manière compétitive. Finalement, nous proposons la première implémentation d'applications multilinéaires et réalisons, pour la première fois, un échange de clé non interactif entre plus de trois participants en quelques secondes.

L’Internet des Objets (IoT, Internet of Things) est un réseau diversifié d’objets interconnectés, généralement via l’internet. En raison de la sensibilité des informations échangées dans les applications de IoT, il est essentiel de garantir la sécurité et le respect de la vie privée. Ce problème est aggravé par la nature ouverte des communications sans fil et par les contraintes de puissance et de ressources computationnelles de la plupart des appareils IoT. Parallèlement, les solutions de sécurité IoT existantes sont basées sur des architectures centralisées, ce qui pose des problèmes d’évolutivité et de point de défaillance unique, les rendant sensibles aux attaques par déni de service et aux défaillances techniques. La Blockchain est considérée comme une solution attractive aux problèmes de sécurité et de centralisation de IoT. Les Blockchains reproduisent un enregistrement permanent, en annexe seulement, de toutes les transactions effectuées sur un réseau entre plusieurs appareils, en les maintenant synchronisées par un protocole de consensus. L’utilisation de la Blockchain peut impliquer des coûts de calcul et d’énergie élevés pour les appareils. Par conséquent, des solutions basées sur Fog/Edge Computing ont été envisagées dans le cadre de l’intégration avec l’IoT. Cette approche transfère la charge de calcul et la consommation d’énergie plus élevées vers les dispositifs ayant une plus grande disponibilité de ressources, les dispositifs Fog/Edge. Toutefois, le coût de l’utilisation de la Blockchain doit être optimisé, en particulier dans le protocole de consensus, qui influe considérablement sur les performances globales du système. Les Blockchains avec permission correspondent mieux aux exigences des applications IoT que les Blockchains sans permission, en raison de leur taux élevé de traitement des transactions et de leur scalabilité. En effet, les nœuds de consensus, les validateurs, sont connus et prédéterminés. Dans les protocoles de consensus existants utilisés dans les Blockchains avec permission, les validateurs sont généralement un ensemble de nœuds prédéfinis ou sélectionnés de manière aléatoire, ce qui affecte à la fois les performances du système et l’équité (Fairness) entre les utilisateurs. L’objectif de ce travail est de proposer des solutions pour améliorer la sécurité et la vie privée dans IoT en intégrant la technologie Blockchain, ainsi que pour maximiser les niveaux de fairness pendant le consensus. L’étude est organisée en deux parties distinctes : l’une traite des aspects critiques de la sécurité de IoT et propose des solutions basées sur la Blockchain, tandis que l’autre se concentre sur l’optimisation de la Fairness entre les utilisateurs lors de l’exécution de l’algorithme de consensus sur la Blockchain. Nous présentons un mécanisme d’authentification inspiré du protocole d’authentification µTesla, qui utilise des clés symétriques formant une chaîne de hachage et obtient des propriétés asymétriques en dévoilant la clé utilisée un peu plus tard. Grâce à ce mécanisme et à l’utilisation de la Blockchain pour stocker les clés et faciliter l’authentification, notre proposition garantit une authentification robuste et efficace des appareils, sans qu’il soit nécessaire de recourir à un tiers de confiance. En outre, nous présentons un système de gestion des clés basé sur la Blockchain pour les communications de groupe, adapté aux contextes de IoT. L’utilisation de la cryptographie à courbe elliptique garantit un faible coût de calcul tout en permettant une distribution sécurisée des clés de groupe. Dans les deux solutions de sécurité, nous fournissons des preuves formelles et informelles de la sécurité dans le modèle d’attaque défini. Une analyse de l’impact sur la performance et une comparaison avec les solutions existantes sont également menées pour les solutions proposées, montrant que les solutions proposées sont sûres et efficaces et peuvent être utilisées dans de multiples applications IoT
The Internet of Things (IoT) is a diverse network of objects typically interconnected via the Internet. Given the sensitivity of the information exchanged in IoT applications, it is essential to guarantee security and privacy. This problem is aggravated by the open nature of wireless communications, and the power and computing resource limitations of most IoT devices. Existing IoT security solutions are based on centralized architectures, which raises scalability issues and the single point of failure problem, making them susceptible to denial-of-service attacks and technical failures. Blockchain has emerged as an attractive solution to IoT security and centralization issues. Blockchains replicate a permanent, append-only record of all transactions occurring on a network across multiple devices, keeping them synchronized through a consensus protocol. Blockchain implementation may involve high computational and energy costs for devices. Consequently, solutions based on Fog/Edge computing have been considered in the integration with IoT. However, the cost of Blockchain utilization must be optimized, especially in the consensus protocol, which significantly influences the overall system performance. Permissioned Blockchains align better with the requirements of IoT applications than Permissionless Blockchains, due to their high transaction processing rate and scalability. This is because the consensus nodes, i.e., Validators, are known and predetermined. In existing consensus protocols used in Permissioned Blockchains, the Validators are usually a predefined or randomly selected set of nodes, which affects both system performance and fairness among users. The objective of this work is to propose solutions to improve security and privacy within IoT by integrating Blockchain technology, as well as to maximize fairness levels during consensus. The study is organized into two distinct parts: one addresses critical aspects of IoT security and proposes Blockchain-based solutions, while the other part focuses on optimizing fairness among users during the execution of the consensus algorithm on the Blockchain. We present an authentication mechanism inspired by the µTesla authentication protocol, which uses symmetric keys that form a hashchain and achieves asymmetric properties by unveiling the key used a while later. With this mechanism and the use of the Blockchain to store the keys and facilitate authentication, our proposal ensures robust and efficient authentication of devices, without the need for a trusted third party. In addition, we introduce a Blockchain-based key management system for group communications adapted to IoT contexts. The use of Elliptic Curve Cryptography ensures a low computational cost while enabling secure distribution of group keys. In both security solutions, we provide formal and informal proofs of security under the defined attack model. A performance impact analysis and a comparison with existing solutions are also conducted, showing that the proposed solutions are secure and efficient and can be used in multiple IoT applications. The second part of the work proposes an algorithm to select Validator nodes in Permissioned Blockchains maximizing Social Welfare, using α-Fairness as the objective function. A mathematical model of the problem is developed, and a method for finding the solution in a distributed manner is proposed, employing metaheuristic Evolutionary algorithms and a Searchspace partitioning strategy. The security of the proposed algorithm and the quality of the solutions obtained are analyzed. As a result of this work, two security protocols for IoT based on Blockchain are introduced, along with a distributed algorithm for maximizing Social Welfare among users in a Permissioned Blockchain network

L'apprentissage automatique en tant que service (MLaaS) fait référence à un service qui permet aux entreprises de déléguer leurs tâches d'apprentissage automatique à un ou plusieurs serveurs puissants, à savoir des serveurs cloud. Néanmoins, les entreprises sont confrontées à des défis importants pour garantir la confidentialité des données et le respect des réglementations en matière de protection des données. L'exécution de tâches d'apprentissage automatique sur des données sensibles nécessite la conception de nouveaux protocoles garantissant la confidentialité des données pour les techniques d'apprentissage automatique.Dans cette thèse, nous visons à concevoir de tels protocoles pour MLaaS et étudions trois techniques d'apprentissage automatique : les réseaux de neurones, le partitionnement de trajectoires et l'agrégation de données. Dans nos solutions, notre objectif est de garantir la confidentialité des données tout en fournissant un niveau acceptable de performance et d’utilité. Afin de préserver la confidentialité des données, nous utilisons plusieurs techniques cryptographiques avancées : le calcul bipartite sécurisé, le chiffrement homomorphe, le rechiffrement proxy homomorphe ainsi que le chiffrement à seuil et le chiffrement à clé multiples. Nous avons en outre implémenté ces nouveaux protocoles et étudié le compromis entre confidentialité, performance et utilité/qualité pour chacun d’entre eux
Machine Learning as a Service (MLaaS) refers to a service that enables companies to delegate their machine learning tasks to single or multiple untrusted but powerful third parties, namely cloud servers. Thanks to MLaaS, the need for computational resources and domain expertise required to execute machine learning techniques is significantly reduced. Nevertheless, companies face increasing challenges with ensuring data privacy guarantees and compliance with the data protection regulations. Executing machine learning tasks over sensitive data requires the design of privacy-preserving protocols for machine learning techniques.In this thesis, we aim to design such protocols for MLaaS and study three machine learning techniques: Neural network classification, trajectory clustering, and data aggregation under privacy protection. In our solutions, our goal is to guarantee data privacy while keeping an acceptable level of performance and accuracy/quality evaluation when executing the privacy-preserving variants of these machine learning techniques. In order to ensure data privacy, we employ several advanced cryptographic techniques: Secure two-party computation, homomorphic encryption, homomorphic proxy re-encryption, multi-key homomorphic encryption, and threshold homomorphic encryption. We have implemented our privacy-preserving protocols and studied the trade-off between privacy, efficiency, and accuracy/quality evaluation for each of them

Une des avancées les plus notables de ces dernières années en cryptographie est sans contredit l’introduction du premier schéma de chiffrement complètement homomorphe par Craig Gentry. Ce type de système permet de réaliser des calculs arbitraires sur des données chiffrées, sans les déchiffrer. Cette particularité permet de répondre aux exigences de sécurité et de protection des données, par exemple dans le cadre en plein développement de l'informatique en nuage et de l'internet des objets. Les algorithmes mis en œuvre sont actuellement très coûteux en temps de calcul, et généralement implantés sous forme logicielle. Les travaux de cette thèse portent sur l’accélération matérielle de schémas de chiffrement homomorphes. Une étude des primitives utilisées par ces schémas et la possibilité de leur implantation matérielle est présentée. Ensuite, une nouvelle approche permettant l’implantation des deux fonctions les plus coûteuses est proposée. Notre approche exploite les capacités offertes par la synthèse de haut niveau. Elle a la particularité d’être très flexible et générique et permet de traiter des opérandes de tailles arbitraires très grandes. Cette particularité lui permet de viser un large domaine d’applications et lui autorise d’appliquer des optimisations telles que le batching. Les performances de notre architecture de type co-conception ont été évaluées sur l’un des cryptosystèmes homomorphes les plus récents et les plus efficaces. Notre approche peut être adaptée aux autres schémas homomorphes ou plus généralement dans le cadre de la cryptographie à base de réseaux
One of the most significant advances in cryptography in recent years is certainly the introduction of the first fully homomorphic encryption scheme by Craig Gentry. This type of cryptosystem allows performing arbitrarily complex computations on encrypted data, without decrypting it. This particularity allows meeting the requirements of security and data protection, for example in the context of the rapid development of cloud computing and the internet of things. The algorithms implemented are currently very time-consuming, and most of them are implemented in software. This thesis deals with the hardware acceleration of homomorphic encryption schemes. A study of the primitives used by these schemes and the possibility of their hardware implementation is presented. Then, a new approach allowing the implementation of the two most expensive functions is proposed. Our approach exploits the high-level synthesis. It has the particularity of being very flexible and generic and makes possible to process operands of arbitrary large sizes. This feature allows it to target a wide range of applications and to apply optimizations such as batching. The performance of our co-design was evaluated on one of the most recent and efficient homomorphic cryptosystems. It can be adapted to other homomorphic schemes or, more generally, in the context of lattice-based cryptography

Les schémas de Chiffrement Complètement Homomorphe (FHE) permettent de manipuler des données chiffrées avec grande flexibilité : ils rendent possible l'évaluation de fonctions à travers les couches de chiffrement. Depuis la découverte du premier schéma FHE en 2009 par Craig Gentry, maintes recherches ont été effectuées pour améliorer l'efficacité, atteindre des nouveaux niveaux de sécurité, et trouver des applications et liens avec d'autres domaines de la cryptographie. Dans cette thèse, nous avons étudié en détail ce type de schémas. Nos contributions font état d'une nouvelle attaque de récuperation des clés au premier schéma FHE, et d'une nouvelle notion de sécurité en structures hierarchiques, évitant une forme de trahison entre les usagers tout en gardant la flexibilité FHE. Enfin, on décrit aussi des implémentations informatiques. Cette recherche a été effectuée au sein du Laboratoire de Mathématiques de Versailles avec le Prof. Louis Goubin
Fully Homomorphic Encryption schemes allow public processing of encrypted data. Since the groundbreaking discovery of the first FHE scheme in 2009 by Craig Gentry, an impressive amount of research has been conducted to improve efficiency, achieve new levels of security, and describe real applications and connections to other areas of cryptography. In this Dissertation, we first give a detailed account on research these past years. Our contributions include a key-recovery attack on the ideal lattices FHE scheme and a new conception of hierarchic encryption, avoiding at some extent betrayal between users while maintaining the flexibility of FHE. We also describe some implementations. This research was done in the Laboratoire de Mathématiques de Versailles, under supervision of Prof. Louis Goubin

Les protocoles de dissémination de contenus randomisés sont une alternative bon marché et pouvant monter en charge aux systèmes centralisés. Cependant, il est bien connu que ces protocoles souffrent en présence de comportements individualistes, i.e., de participants qui cherchent à recevoir un contenu sans contribuer en retour à sa propagation. Alors que le problème des participants égoïstes a été bien étudié dans la littérature, les coalitions de participants égoïstes ont été laissés de côté. De plus, les manières actuelles permettant de limiter ou tolérer ces comportements exigent des noeuds qu'ils enregistrent leurs interactions, et rendent public leur contenu, ce qui peut dévoiler des informations gênantes. De nos jours, il y a consensus autour du besoin de renforcer les possibilités de contrôle des usagers de systèmes informatiques sur leurs données personnelles. Cependant, en l'état de nos connaissances, il n'existe pas de protocole qui évite de divulguer des informations personnelles sur les utilisateurs tout en limitant l'impact des comportements individualistes.Cette thèse apporte deux contributions.Tout d'abord, nous présentons AcTinG, un protocole qui empêche les coalitions de noeuds individualistes dans les systèmes pair-à-pair de dissémination de contenus, tout en garantissant une absence de faux-positifs dans le processus de détection de fautes. Les utilisateurs de AcTinG enregistrent leurs interactions dans des enregistrements sécurisés, et se vérifient les uns les autres grâce à une procédure d'audit non prédictible, mais vérifiable a posteriori. Ce protocole est un équilibre de Nash par construction. Une évaluation de performance montre qu'AcTinG est capable de fournir les messages à tous les noeuds malgré la présence de coalitions, et présente des propriétés de passage à l'échelle similaires aux protocoles classiques de dissémination aléatoire.Ensuite, nous décrivons PAG, le premier protocole qui évite de dévoiler des informations sur les usagers tout en les contrôlant afin d'éviter les comportements égoïstes. PAG se base sur une architecture de surveillance formée par les participants, ainsi que sur des procédures de chiffrement homomorphiques. L'évaluation théorique de ce protocole montre qu'obtenir le détail des interactions des noeuds est difficile, même en cas d'attaques collectives. Nous évaluons ce protocole en terme de protection de l'intimité des interactions et en terme de performance en utilisant un déploiement effectué sur un cluster de machines, ainsi que des simulations qui impliquent jusqu'à un million de participants, et enfin en utilisant des preuves théoriques. Ce protocole a un surcoût en bande-passante inférieur aux protocoles de communications anonymes existants, et est raisonnable en terme de coût cryptographique
Gossip-based content dissemination protocols are a scalable and cheap alternative to centralised content sharing systems. However, it is well known that these protocols suffer from rational nodes, i.e., nodes that aim at downloading the content without contributing their fair share to the system. While the problem of rational nodes that act individually has been well addressed in the literature, textit{colluding} rational nodes is still an open issue. In addition, previous rational-resilient gossip-based solutions require nodes to log their interactions with others, and disclose the content of their logs, which may disclose sensitive information. Nowadays, a consensus exists on the necessity of reinforcing the control of users on their personal information. Nonetheless, to the best of our knowledge no privacy-preserving rational-resilient gossip-based content dissemination system exists.The contributions of this thesis are twofold.First, we present AcTinG, a protocol that prevents rational collusions in gossip-based content dissemination protocols, while guaranteeing zero false positive accusations. AcTing makes nodes maintain secure logs and mutually check each others' correctness thanks to verifiable but non predictable audits. As a consequence of its design, it is shown to be a Nash-equilibrium. A performance evaluation shows that AcTinG is able to deliver all messages despite the presence of colluders, and exhibits similar scalability properties as standard gossip-based dissemination protocols.Second, we describe PAG, the first accountable and privacy-preserving gossip protocol. PAG builds on a monitoring infrastructure, and homomorphic cryptographic procedures to provide privacy to nodes while making sure that nodes forward the content they receive. The theoretical evaluation of PAG shows that breaking the privacy of interactions is difficult, even in presence of a global and active opponent. We assess this protocol both in terms of privacy and performance using a deployment performed on a cluster of machines, simulations involving up to a million of nodes, and theoretical proofs. The bandwidth overhead is much lower than existing anonymous communication protocols, while still being practical in terms of CPU usage