Project Topics
Get Complete Project Material File(s) Now! »
Contexte historique et motivations
Bien que déjà utilisée pendant l’Antiquité, la cryptologie – étymologiquement science du secret n’a justifié son statut de science que récemment grâce aux fondations théoriques posées par Shannon à la fin des années 40 ([Sha49]), et l’avènement de la cryptographie à clé publique dans les années 70. Elle se divise en deux disciplines de nature opposées mais complémentaires : la cryptographie et la cryptanalyse.
La première a pour but de protéger des communications, pour cela il lui faut garantir quatre propriétés : la confidentialité, l’authenticité, l’intégrité et la non-répudiation de celles-ci. La première propriété garantie que seuls les participants à la communication aient accès aux messages. L’authenticité permet d’assurer l’identité des entités qui y participent, tandis que l’intégrité est nécessaire afin de garantir qu’un message n’ait pas été altéré par un tiers non autorisé. Enfin la non-répudiation a pour but d’empêcher que l’une des entités participant à la communication puisse nier l’avoir fait. Afin d’assurer ces propriétés en pratique, les participants à la communication doivent être en possession d’un secret ou clé.
La cryptanalyse de manière opposée, a pour but de récupérer des informations à partir d’une communication protégée afin de corrompre l’une, ou plusieurs, des quatre propriétés précédentes et ce sans avoir nécessairement connaissance de la clé.
Historiquement la cryptographie avait surtout pour but d’assurer la confidentialité des messages, les autres propriétés sont essentiellement apparues avec la cryptographie moderne et sont d’autant plus importantes de nos jours avec l’internet. La confidentialité d’un message est assurée en utilisant une clé, afin de le rendre inintelligible à toute personne ne connaissant pas la clé. On parle alors de messages chiffré.
En cas de guerre, il est essentiel de s’assurer qu’un message intercepté demeure inintelligible pour l’adversaire. C’est pourquoi historiquement les innovations en matière de chiffrement et de cryptanalyse sont principalement apparues au cours de différents conflits. Parmi les chiffrements célèbres nous pouvons citer la scytale utilisée par les Spartiates lors de la guerre du Péloponnèse, ou encore le chiffrement de César utilisé par les Romains lors de la guerre des Gaules.
Plus récemment, lors des deux grands conflits du XXème siècle, la cryptologie eut une importance décisive. En 1917, les renseignements Britanniques ont intercepté et déchiffré un télégramme du ministre allemand des affaires étrangères, Arthur Zimmermann, envoyé à l’ambassadeur allemand au Mexique dans lequel l’Allemagne proposait une alliance au Mex-ique. Les termes de cette alliance spécifiaient que le Mexique devrait envahir le sud des États-Unis, si jamais ceux-ci venaient à abandonner leur neutralité, afin de les empêcher d’intervenir en Europe. La révélation de ce télégramme poussa les États-Unis à déclarer la guerre à l’Allemagne et précipita la fin du conflit. Lors de la deuxième guerre mondiale, la machine Enigma, utilisée par les Allemands pour chiffrer leurs communications fut le premier exemple de chiffrement mécanique de l’histoire. Sa cryptanalyse, par l’équipe d’Alan Turing en 1940 nécessita quant à elle la construction du premier ordinateur de l’histoire. Une fois le chiffrement cassé, les Alliés disposèrent d’un avantage certain sur la suite du conflit. La cryptologie venait d’entrer dans l’ère moderne.
Jusqu’à la seconde moitié du XXème siècle, la même clé était utilisée pour chiffrer et déchiffrer les messages ; on parle alors de cryptographie symétrique. Ce type de chiffre-ment souffre toutefois d’un inconvénient majeur puisqu’il nécessite que les partis souhaitant communiquer aient échangé la clé de chiffrement, de manière sécurisée, avant le début de la communication. Le problème est alors d’échanger cette clé de manière sécurisée. Ce problème fut solutionné dans les années 70 par l’invention du concept de la cryptographie asymétrique, ou encore cryptographie à clé publique, par W. Diffie et M. Hellman ([DH76]), et de manière moins connue par R. Merkle ([Mer78]).
La cryptographie à clé publique repose sur le principe que la personne qui doit déchiffrer le message génère deux clés. La première est une clé secrète, qui comme son nom l’indique doit rester secrète, la seconde est une clé qui est rendue publique. Cette clé publique est utilisée par quiconque souhaitant envoyer un message, de manière sécurisée, au détenteur de la clé secrète afin de chiffrer son message. En revanche, ce dernier est le seul à être capable de déchiffrer le message grâce à la clé secrète. Si ces deux clés sont bien évidemment liées entre elles, on s’assure qu’on ne puisse pas retrouver facilement la clé secrète à partir de la clé publique en faisant en sorte que cela revienne à résoudre un problème calculatoire difficile.
Une bonne analogie à la cryptographie à clé publique est une boite aux lettres. Tout le monde peut facilement glisser un message dans une boite aux lettres. Par contre il est très difficile de récupérer les messages si l’on ne possède pas la clé qui l’ouvre, seul le propriétaire de la boite est en mesure de récupérer les messages facilement.
Dans le contexte de la cryptologie, les mots «facile» ou «difficile» doivent être compris au sens calculatoire du terme, facile signifiant qu’il existe un algorithme permettant de résoudre n’importe quelle instance du problème en temps polynomial tandis que difficile signifie que ce n’est pas facile. Pour des raisons de sécurité il faut que retrouver la clé secrète à partir de la clé publique soit difficile, mais pour des raisons pratiques on souhaite pouvoir déduire la clé publique de la clé secrète facilement.
Ainsi, la cryptographie à clé publique repose sur des problèmes calculatoires qui sont faciles à résoudre dans un sens mais difficile dans l’autre. Un bon exemple d’un tel problème est la multiplication/factorisation de deux nombres entiers. Multiplier deux entiers se fait facilement, par exemple il n’est pas difficile de trouver que 41 37 = 1517, en revanche il est moins évident de trouver que 2021 est en fait le produit de 43 et de 47.
C’est précisément en s’appuyant sur ce problème qu’en 1978, R. Rivest, A. Shamir et L. Adleman ont créé leur système de chiffrement, baptisé RSA, qui fut la première construction concrète d’un chiffrement à clé publique ([RSA78]). Une propriété notable du RSA est que lorsque l’on multiplie deux chiffrés, de deux messages différents, entre eux on obtient alors un chiffré du produit des deux messages. Cette propriété qui permet d’effectuer des opérations sur les messages directement à travers leurs chiffrés, sans avoir à les déchiffrer au préalable, est appelée propriété homomorphe.
Dès lors, la question s’est posée de savoir s’il était possible, ou non, de construire un schéma généralisant la propriété homomorphe multiplicative du RSA, c’est à dire un chiffre-ment permettant d’effectuer tout type d’opérations sur les messages directement à travers leurs chiffrés ([RAD78]). On parlera plus tard de chiffrement complètement homomorphe.
La question de savoir s’il était possible ou non de construire un schéma de chiffrement com-plètement homomorphe resta ouverte durant de nombreuses années. Sachant que n’importe quelle fonction continue peut s’approximer par un polynôme sur un compact, il suffit en pra-tique de pouvoir évaluer des polynômes de manière homomorphique. Pour cela il est seulement nécessaire de disposer d’additions et de multiplications homomorphiques. Plusieurs schémas de chiffrement possédant, comme le RSA, une des deux propriétés furent construits dans les années qui suivirent, par exemple ElGamal pour la multiplication ([ElG85]) et Paillier pour l’addition ([Pai99]).
Il a fallu attendre 2005 et les travaux de D. Boneh, E. Goh et K. Nissim pour obtenir la première construction d’un chiffrement possédant les deux propriétés ([BGN05]). Toutefois, cette construction souffre d’un inconvénient majeur puisqu’elle ne permet l’évaluation que d’une seule multiplication de manière homomorphique. Le problème fut finalement solutionné par C. Gentry en 2009, qui proposa la première construction d’un schéma de chiffrement complètement homomorphe permettant l’évaluation d’un nombre arbitraire d’additions et de multiplications et résolvant ainsi un problème de plus de trente ans ([Gen09]).
Cette construction, basée sur les réseaux euclidiens, se déroule en deux temps. La pre-mière étape est la construction d’un schéma de base permettant l’évaluation d’un nombre limité d’additions et de multiplications de manière homomorphique, on parle alors de schéma presque homomorphe. Comme chaque chiffré de ce genre de schéma contient un bruit, on parle de chiffrement bruité. Après chaque opération homomorphe, ce bruit va grossir jusqu’à atteindre une certaine taille au delà de laquelle il ne sera plus possible de déchiffrer le message correctement, d’où le nombre limité d’opérations. La seconde étape est la construction d’une procédure permettant de réduire la taille du bruit d’un chiffré lorsque celle-ci devient trop im-portante. Cette technique, appelée «bootstrapping», consiste à évaluer homomorphiquement le circuit de déchiffrement du schéma. Ainsi, à la fin de la procédure, on obtient un nouveau chiffré du même message, avec un bruit de même taille que si l’on avait évalué homomorphique-ment le circuit de déchiffrement à partir d’un chiffré «frais». Sachant que l’augmentation du bruit après une multiplication est plus importante qu’après une addition, si le schéma de base permet d’effectuer homomorphiquement une multiplication en plus de l’évaluation de son cir-cuit de déchiffrement, il est dit «bootstrappable» et peut donc être transformé en un schéma complètement homomorphe.
De nos jours, ce genre de chiffrement pourrait avoir un impact considérable sur la protec-tion de la vie privée notamment avec l’essor du «cloud computing». Le chiffrement homomor-phe offre une solution concrète à différents problèmes apparaissant en cryptographie comme le calcul multipartite sécurisé, la délégation de calculs ou encore le vote électronique. Mal-heureusement, bien que théoriquement correcte, la première construction de Gentry requiert de tels paramètres qu’elle est inutilisable en pratique.
C’est pourquoi, dans les années qui suivirent, la communauté consacra des efforts impor-tants à améliorer cette première construction de sorte à la rendre implémentable, ce qui fut accomplit en 2011 ([GH11]). Cette première implémentation fut toutefois rapidement rendue obsolète par l’arrivée des schémas, dit de deuxième génération, qui furent construit les an-nées suivantes. Citons par exemple : Brakerski-Gentry-Vaikuntanathan (BGV) ([BGV12]), Brakerski «scale-invariant» ([Bra12]) ou encore Gentry-Sahai-Waters (GSW) ([GSW13]). Les meilleures performances obtenues par les schémas susmentionnés sont directement liées au problème sous-jacent sur lequel leur sécurité est basée : le Learning With Errors (LWE).
Ce problème, basé sur les réseaux euclidiens et introduit par O. Regev en 2005 ([Reg05]), est actuellement la structure de base sur laquelle une grande partie des schémas de chiffrement homomorphe sont construits. De manière informelle ce problème consiste à la résolution d’un système linéaire «bruité». Plus précisément, considérons une matrice A et un vecteur s à coefficients entiers dans un grand intervalle centré en zéro [q=2; q=2[. Connaissant la matrice A, la version «décisionnelle» du problème consiste à être capable de déterminer si un vecteur b a ses coefficients tirés uniforméments dans [ q=; q=2[ ou bien s’il est tel que b = As + e mod q), où e est un vecteur de «bruit», i.e. de petits coefficients. De manière équivalente la version «recherche» consiste à retrouver le vecteur s à partir du couple ( A; b = As+e mod q). Notons l’importance du vecteur e, sans lequel ce problème se réduirait une résolution de sys-tème linéaire.
Bien que permettant une augmentation significative des performances par rapport à la pre-mière construction de Gentry, la structure sous-jacente du LWE est loin d’être satisfaisante en pratique. En effet, pour obtenir des niveaux de sécurité suffisants et un schéma «boot-strappable», il est nécessaire d’utiliser des matrices et des vecteurs de grande taille avec de gros coefficients de sorte que les temps de calculs, et les coûts en mémoire, pour manipuler les éléments deviennent trop importants.C’est pourquoi, très rapidement, la communauté académique s’est mise à considérer dif-férentes variantes de ce problème, et en particulier sa version sur les anneaux appelée Ring-Learning With Errors (Ring-LWE) ou encore Learning With Errors over Rings qui est basée sur les réseaux idéaux ([LPR10]). Dans cette version, la matrice A du LWE est remplacée par un élément a de l’anneau Rq = (Z=qZ)[X]=(f) où f est un polynôme unitaire et irréductible de degré n. Les vecteurs s et e sont à présent considérés comme des éléments de Rq. Le problème est alors similaire : déterminer si un couple d’éléments (a; b) 2 Rq2 a été tiré de manière uniforme dans Rq, ou bien s’il existe des éléments s et e tels que b = a s + e. Il y a deux bénéfices principaux à cette variante : a est désormais représenté par n coefficients au lieu de n2, ce qui permet de gagner un facteur n sur la complexité en mémoire ;
plutôt que d’avoir à effectuer des produits matrice vecteur (complexité asymptotique O(n2)), on multiplie à présent des éléments de Rq ce qui peut être fait plus efficacement (complexité asymptotique O(n log n)), en particulier lorsque f ( X ) = X n + 1 pour n une puissance de deux.
Les schémas de chiffrements homomorphes basés sur le LWE se transcrivent assez na-turellement au Ring-LWE, ce qui permet d’améliorer significativement leurs performances. Le schéma BGV a été développé directement pour les deux problèmes, la construction de Brak-erski a été adaptée au Ring-LWE par J. Fan et F. Vercauteren et fut renommée d’après ses auteurs FV ([FV12]), l’adaptation de GSW fut, quant à elle, renommée SHIELD ([KGV16]). Les problèmes du LWE et du Ring-LWE se réduisent tout deux, sous certaines conditions, des problèmes difficiles sur les réseaux; euclidiens et idéaux respectivement. Pour l’instant aucun algorithme permettant de résoudre le Ring-LWE plus efficacement que le LWE n’est connu, en fait la cryptanalyse concrète d’une instance de Ring-LWE se fait en cryptanalysant une instance de LWE déduite de cette dernière. Dans ce cas les coefficients de a 2 Rq forment la première colonne de la matrice A et les colonnes restantes se déduisent à partir de la première en utilisant la structure du polynôme f.
Néanmoins les avantages apportés par le Ring-LWE ne sont pas sans conséquence poten-tielle. En effet, il est fortement soupçonné que la structure additionnelle présente dans les réseaux idéaux, qui provient du polynôme f, puisse être exploitée afin de résoudre des prob-lèmes dans ce genre de réseaux de manière plus efficace. C’est pourquoi, et ce bien qu’on ne sache toujours pas si cette structure peut être exploitée ou pas, il est fortement pressenti que le problème du Ring-LWE est moins difficile que celui du LWE.
En pratique le bootstrapping de Gentry est la procédure la plus coûteuse, ainsi on essaye généralement de l’utiliser le moins possible. Une façon de procéder est de sélectionner des paramètres de schéma presque homomorphe de sorte à pouvoir effectuer toutes les opérations requises par une application particulière, et connue à l’avance, sans utiliser le bootstrapping ([BGV12]).
Toutefois, dans un travail remarquable, L. Ducas et D. Micciancio ont construit un schéma, appelé FHEW, basé sur le Ring-LWE avec lequel le bootstrapping peut être effectué de manière efficace – moins d’une seconde ([DM15]). En introduisant une variante du Ring-LWE sur le tore réel, Chillotti et al. ont amélioré FHEW, qui est devenu TFHE, jusqu’à obtenir un temps de 0.1 seconde pour le bootstrapping ([CGGI16]). Dans leur contexte, le bootstrapping est effectué après chaque évaluation d’une porte logique, ils peuvent ainsi évaluer homomor-phiquement autant de portes qu’ils le souhaitent obtenant ainsi un chiffrement complètement homomorphe très compétitif.
Enfin, il est probablement important de mentionner qu’après des années de recherche et de développement dans les laboratoires académiques, l’ordinateur quantique n’est plus un rêve fantaisiste. Son arrivée prochaine va confronter la cryptologie moderne à la première grande révolution de sa jeune histoire.
En effet, avec un tel ordinateur, les problèmes calculatoires sur lesquels repose la sécurité des systèmes de chiffrements utilisés à l’heure actuelle (factorisation et logarithme discret) pourront être résolus en temps polynomial ([Sho97]). Ainsi, tous les chiffrements basés sur ces problèmes ne seront plus sûrs. Il devient donc nécessaire de développer de nouveaux chiffrements qui soient basés sur des problèmes que l’ordinateur quantique ne pourra pas résoudre en temps polynomial. L’appel récent de la National Institute of Standards and Technology (NIST), afin de poser les bases des futurs standards de la cryptographie post-quantique va dans ce sens.
Dans cette perspective, les problèmes basés sur les réseaux (euclidiens ou idéaux) sont de bons candidats puisqu’on ne connaît pas, à ce jour, d’algorithme quantique permettant de les résoudre de manière significativement plus efficace. Ainsi le chiffrement homomorphe n’est pas compromis à moyen terme par l’arrivée de l’ordinateur quantique. En revanche, l’utilisation de ce genre de chiffrement est toujours limitée en pratique par les coûts importants qu’il nécessite, que ce soit en temps ou en mémoire.
But et organisation de la thèse
Le but de cette thèse est d’optimiser l’arithmétique sous-jacente à plusieurs schémas de chiffre-ments presque homomorphes basés sur le problème du Ring-LWE afin d’améliorer leur per-formances. Nous espérons contribuer ainsi à lever une partie des barrières qui empêchent toujours l’utilisation de ce type de chiffrement en pratique. Pour cela, nous nous sommes concentrés sur deux points : l’optimisation de l’arithmétique utilisée par les primitives de ces schémas, qu’il s’agisse d’opérations intrinsèques à leurs primitives, ou bien d’opérations requises dans le con-texte plus général du Ring-LWE ;
optimiser les calculs spécifiques à une utilisation concrète de ce type de chiffrement, que ce soit au niveau des algorithmes utilisés ou de leurs implémentations.
Le chapitre 1 a pour but d’introduire les différentes notions nécessaires à la bonne com-préhension de la suite de ce manuscrit. Pour cela nous commençons par introduire brièvement le problème du Ring-LWE dans le cas des corps cyclotomiques tout en mettant en évidence son lien avec les réseaux idéaux. Dans une deuxième partie, nous présentons deux des schémas de chiffrements homomorphes les plus couramment utilisés : BGV et FV, tous deux basés sur le problème du Ring-LWE. Enfin dans une dernière partie, nous présentons les différents outils utilisés afin d’effectuer les opérations requises par ce genre de chiffrement de manière efficace.
La première contribution ([BEHZ17]) de cette thèse est présentée dans le chapitre 2. Ce travail s’est concentré sur l’utilisation du système de représentation des nombres par les restes (RNS). La représentation RNS permet d’effectuer des additions et multiplications sur de grands nombres de manière très efficace, ce qui est très utile dans le contexte du chiffrement homomorphe. Malheureusement, d’autres opérations comme par exemple les comparaisons ne peuvent pas être effectuées directement en RNS. En surmontant les limitations de cette représentation, nous avons réussi à effectuer l’ensemble des calculs nécessaires aux différentes procédures des schémas de chiffrement homomorphe de type «scale-invariant» comme FV. Cela s’est traduit par une amélioration remarquable des performances de ces schémas.
L’efficacité de l’arithmétique dans l’espace Rq = (Z=qZ)[X]=(f) dépend fortement de f no-tamment à cause de la réduction modulo ce polynôme. Cette efficacité est maximale lorsque est un cyclotomique de la forme X n +1. En revanche ce type de polynômes entraîne d’autres limitations qui, selon l’application voulue, peuvent nécessiter de considérer d’autres types de cyclotomiques. Le chapitre 3, présente un travail dans lequel nous nous sommes concentrés à améliorer l’efficacité de l’opération de réduction par le polynôme f, lorsque celui-ci est un cyclotomique différent de X n + 1 ([BEH+18]). Cette opération étant nécessaire pour chaque produit d’éléments dans Rq, son optimisation a permis d’augmenter significativement les per-formances des primitives des schémas BGV et FV dans ces cas là.
Finalement dans le quatrième et dernier chapitre nous présentons une application concrète d’utilisation de chiffrement homomorphe pour la classification de données privées ([BMSZ18]). De nos jours ce genre de classification utilise de plus en plus des méthodes d’apprentissages automatiques et notamment des machines à vecteurs de support (MVS). Évaluer homomor-phiquement une MVS permet de classer des données sans jamais avoir à révéler celles-ci. Nous commençons par présenter le fonctionnement de ces MVS qui sont des techniques ap-partenant au domaine de l’apprentissage supervisé. Dans un deuxième temps nous exposons les méthodes algorithmiques que nous avons utilisées afin d’effectuer homomorphiquement les opérations requises par ces techniques. L’efficacité de nos méthodes est illustrée par des implémentations sur différents type d’architectures.
Enfin dans une dernière partie nous présentons les conclusions de cette thèse ainsi que les perspectives qu’elle nous permet d’envisager.
Historical context and motivations
Although already used during ancient times, cryptology – etymologically science of secret – only justified its science status recently with its theoritical foundations laid out by Shannon at the end of the 1940s ([Sha49]), and the advent of public-key cryptography (1970s). It can be split into two mains areas of study which are opposite by nature but complementary: cryptography and cryptanalysis.
The first is about protecting communications from unauthorized third parties, requiring four properties: confidentiality, authentication, data integrity and non-repudiation. Confi-dentiality guaranties that only authorized people can access the messages. The purpose of authentication is to certify the identity of the participants, while data integrity is required to ensure that messages were not corrupted by any unauthorized third party. Finally non-repudiation prevents participants in the communication from falsy denying their implication. In practice, participants of a communication need to possess a secret, also called key, to ensure these properties.
On the other hand, cryptanalysis aims at retrieving some information from a secure com-munication in order to corrupt one, or several, of the previous four properties and this, without necessarily knowing the key.
Historically cryptography was mainly about ensuring the confidentiality of messages. The other properties too are integral to modern cryptography and particularly in the current internet era. Confidentiality of a message is ensured by converting it into an unintelligible text, called ciphertext, by using a key. From there, the message can only be understood by people with knowledge of the key.
During war, it is essential to ensure that encrypted messages remain undecipherable to the adversary in the eventuality where they are intercepted. This is why historically most progress in encryption techniques and cryptanalysis appeared during different conflicts. Among the famous classical encryption methods we can mention the scytale used by the Spartans during the Peloponnesian War, and the Caesar cipher used by the Romans during the Gallic Wars.
More recently, during the two major conflicts of the XXth century, cryptology has been decisive. In 1917, British intelligence intercepted and decrypted a telegram sent by the Ger-man foreign secretary, Arthur Zimmermann, to the German ambassador in Mexico in which Germany was offering an alliance to Mexico. The terms of this alliance specified that Mexico should invade the south of the United States in order to prevent Americans from taking action in Europe in case the United States dropped their neutrality. Once the United States were aware of the content of this telegram they declared war to Germany which sped up the end of the conflict. During World War II the Enigma machine, used by the Germans to encipher their communications, was the first mechanic cipher machine in history. Its cryptanalysis by Alan Turing’s team in 1940 has itself required the construction of the first computer in history. Once Enigma was broken, the Allies had a significant advantage for the rest of the conflict. Cryptology just entered its modern era.
Until the second half of the XXth century, the same key was used to encrypt and decrypt messages: the case referred to as symmetric cryptography. However symmetric cryptography suffers from a major drawback since it requires the parties wishing to communicate have exchanged the cipher key before the communication starts. The problem is therefore to exchange this key in a secure way. This was addressed in the seventies when W. Diffie and M. Hellman proposed the concept of asymmetric cryptography, also called public key cryptography ([DH76]). One should probably mention it was also proposed, roughly at the same time, by R. Merkle even though it is less well-known ([Mer78]).
The principle of public key cryptography is that the person who needs to decrypt messages generates two keys. The first one must remain secret while the second one is made public. The public key is used to encrypt messages by anyone willing to communicate with the owner of the secret key. However the owner of the secret key is the only one able to decrypt the messages encrypted with the corresponding public key. Of course the two keys are related, but it is made sure that one cannot retrieve easily the secret key from the public key unless by solving a difficult computationnal problem.
An analogy for thinking about public key cryptography is a mail box. Everyone can easily put a letter in a mail box, however it is hard to get the letters which are inside the box if you do not have its key. Only the owner of the mail box can easily take the letters inside it.
In the context of cryptology, “easy” and “difficult” must be understood in terms of com-putational complexities. “Easy” means that there exists an algorithm which can solve any instantiation of the problem in polynomial time while “difficult” means that it is not easy. If for security reasons it must be difficult to retrieve the secret key from the public key, for efficiency reasons deriving the public key from the secret key should be easy.
As a consequence, public key cryptography relies on mathematical problems which are easy in one way but difficult on the other. A good example of such a problem is the multipli-cation/factorization of integers. Multiplying two integers is quiet easy, for instance it is not hard to find that 41 37 = 1517, however it is much harder to find out that 2021 is actually the product of 43 and 47.
It is precisely on this problem that in 1978, R. Rivest, A. Shamir and L. Adleman based their encryption/signature scheme, called RSA, which was the first concrete public key con-struction in history ([RSA78]). A noteworthy property of RSA is that when multiplying two ciphertexts, encrypting two different messages, one obtains a ciphertext corresponding to the product of the messages. This property, allowing to process messages directly through their ciphertexts without having to decrypt them beforehand is called homomorphic property.
From there the question whether or not it is possible to construct an encryption scheme generalizing the homomorphic property of RSA arose. This encryption scheme should allow to perform, not only multiplications, but any kind of computations on messages directly through their ciphertexts ([RAD78]). Later this will be referred as Fully Homomorphic En-cryption (FHE).
Whether or not it was possible to construct such a scheme remained opened for many years. Knowing that any continuous function can be approximated over a compact domain by a polynomial, in practice the question can be reduced to being able to evaluate polyno-mials homomorphically. This only requires to perform both additions and multiplications homomorphically. Several encryption schemes allowing to perform one of the two operations like RSA were built in the ensuing years: for instance ElGamal for the multiplication ([ElG85]) and Paillier for the addition ([Pai99]).
The first significant step was made in 2005 by D. Boneh, E. Goh and K. Nissim who con-structed the first encryption scheme possessing the two homomorphic properties ([BGN05]). Nevertheless their construction suffers from a major drawback since it only allows to perform one homomorphic multiplication. In a major breakthrough C. Gentry in 2009 resolved the problem by constructing the first fully homomorphic scheme, i.e. which allows to perform an arbitrary number of additions and multiplications homomorphically, solving a thirty years old problem ([Gen09]).
Its construction, based on euclidean lattices, works through two steps. The first step is the construction of a scheme allowing to perform a limited number of additions and multi-plications. Such restrictive schemes, referred as Somewhat Homomorphic Encryption (SHE), are called “noisy”. In a nutshell, ciphertexts of SHE schemes contains a noise which grows after each homomorphic operation. Unfortunately one is only able to decrypt the message correctly as long as the noise remains small enough, which is the reason why one can only perform a limited number of operations. The second step of Gentry’s construction is a pro-cedure to “refresh” ciphertexts, i.e. which allows to reduce the size of the noise inherent to a ciphertext. This procedure, called “bootstrapping”, roughly consists in running homomor-phically the decryption function. At the end of the procedure, we obtain a new ciphertext, encrypting the same message, whose inherent noise has the same size as if one had evalu-ated the decryption circuit from a “fresh” ciphertext. Noise growth after a multiplication is more important than after an addition. Therefore if the SHE scheme allows to perform one multiplication additionally to the evaluation of its decryption procedure, then the scheme is said “bootstrappable” which means that it can be transformed to a fully homomorphic scheme.
Table of contents :
Introduction (français)
1 Contexte historique et motivations
2 But et organisation de la thèse
Introduction
1 Historical context and motivations
2 Contributions and organization of the report
1 Preliminaries
1.1 Ring-Learning with Errors problem
1.2 Somewhat Homomorphic Encryption based on Ring-LWE
1.3 Classical arithmetic in cyclotomic rings
2 Full RNS scaled-invariant schemes
2.1 Towards a full RNS decryption
2.2 Towards a full RNS homomorphic multiplication
2.3 Last step: the relinearization
2.4 Software implementation
2.5 Conclusion
3 Polynomial arithmetic in general cyclotomic rings
3.1 Preliminaries
3.2 Improving polynomial reduction modulom
3.3 Adaptation of BGV and FV to the Montgomery representation
3.4 Experimental results
3.5 Conclusion
4 Homomorphic evaluation of support vector machine
4.1 Preliminaries
4.2 Novel homomorphic techniques for SVM classification
4.3 Implementation details
4.4 Experimental results
4.5 Conclusion
