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.

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.