Fully Homomorphic Encryption has been around since 2009 and the seminal work of Gentry, nearly thirty years after the concept was imagined. This kind of encryption is that which allows to compute on encrypted data, with the guarantee that the outcomes of the computation, once decrypted, will be the same as if the computation had been done on the un-encrypted data. Since Gentry's work, the community has been tremendously dynamic on this topic and we have seen many scheme proposals which have kept improving the prior works.

The aim of the thesis is to study the gap that remains between the theoretical proposals and the use in real life applications of homomorphic encryption. Our contribution is divided in several topics: the study of the concrete security of the proposals, the comparison of the most promising schemes on a wide range of use cases and the conception and implementation of a new scheme.

To begin, we focus our attention to the cryptanalysis aspects. The security of the homomorphic schemes stands on the ground that the Learning With Errors (LWE) problem is hard. However, for real use we need more than asymptotic hardness result. We want to setup the scheme so that we guarantee say 80 or 128 bits of security. Due to the relative youth of the LWE problem, at cryptographic scale, we still lack hindsight on its concrete security. As our first task, we studied the practical security of LWE, in the cases of homomorphic encryption. We derived a special-purpose attack that we implemented. Our work improved upon the state-of-the-art at that time and our attack showed unexpectedly good performance for some cases.

Once we had gained confidence on how to setup a homomorphic scheme correctly, we could go on to our next task: comparing the existing schemes. Indeed, the details of the different proposals are very technical and for people from outside the cryptographic community (e.g. implementers) it is very hard to know which scheme is the most appropriate. So, we join effort with Vincent Migliore to conduct a comparative survey of the most promising schemes as of 2016. Our aim was to provide a most comprehensive study on different use cases, under different implementation constraints so that we could say which scheme stands out for which situation, and so that implementers could find ready-to-use information.

Last line of work in this thesis, the conception and implementation of a new scheme. I visited at the CWI in Amsterdam in Spring 2017 and worked with Léo Ducas and Max Fillinger on an improvement of FHEW. Our new proposal belongs to the generation of the bootstrapped schemes, that are those where the noise is kept constant between the gates. With our proof-of-concept implementation we can evaluate a binary gate on six input bits 9 with one output bit in roughly six seconds.

Since 2015, we and the community have moved a long way towards practical homomorphic encryption. With the recent performance and the maturity that has been gained, we can expect homomorphic encryption use in real world application within five to ten years.

Perspectives

Quelques astuces d'implémentations pourraient encore être réalisées pour améliorer quelque peu les performances. En revanche, les techniques de RNS, utilisées récemment sur FV, pourraient quant à elles améliorer grandement les performances de notre schéma. Comparativement à TFHE [CGGI17], notre solution n'est en général pas la meilleure. Toutefois sur certains types de portes comme les portes à seuil, notre approche semble meilleure.

Thanks

Mes premiers remerciements vont à ma directrice de thèse, Caroline. La genèse de cette thèse nous ramène en 2013 (et même avant), aussi je la remercie immensément de m'avoir permis d'atteindre cet objectif, grâce notamment à tout son soutien et ses encouragements.

Merci beaucoup à Sylvain et Jacques et Vincent de Thales d'avoir aiguillé les réalisations de cette thèse.

To my reviewers, Frederik and Thomas, I am most grateful for the time they have spent, reading my prosis and providing their great feedbacks. Merci aux examinateurs et invités, Damien, Léo, Adeline, Renaud, Sylvain, Caroline de m'avoir permis de restituer ces trois années de travail.

Comme j'ai pu le constater, l'environnement dans lequel se déroule une thèse est très important. Aussi je salue et je remercie grandement toute la troupe de la Caverne : Benjamin, Thibaud, Bastien, David, Yvon, Xavier, Olivier, Étienne et Arthur, et les personnes qui y sont passées : Pedro, Thomas, Gaël, Erwan, Alex, Guillaume. Merci à Philippe, Patrick, Caroline, David et Yvon pour l'animation et le cadre qu'ils assurent au sein de notre chaire. Pour leur patience et leur support, un grand merci à Magalie, Christine et Amélie, sans qui je n'aurai jamais pu rajouter cette dimension collaborative et m'intégrer si bien dans la communauté.

Big thanks to my co-authors who with I have always had smooth and fruitful collaboration : Caroline, Vincent, Léo, Max, Damien, Teja, Guillaume.

To my fellow fplll development team members: Martin, Marc, Damien, Léo, Shi, Mickael, Koen, a big thanks for the interaction we have had during those coding days in Lyon, interaction that reached beyond lines of codes.

For making my stay there possible, I send my warmest thanks to the CWI staff. Many thanks to Léo for the invitation, to Max for the collaboration and to the whole crypto team: Cécile, Pierre, Marc, Serge, Koen, Ronald and the others I forget! Merci aussi à tous les cryptos français avec qui j'ai eu la chance de discuter au cours de ces trois ans : Julien, Vincent, Soukayna, Adeline, Thomas, Fabrice, Marie, Thierry, Pierre-Alain, Renaud, Malika, Phong, Pauline, Chen, Rachel, Kim, Pascal.

Et puisqu'une thèse ce n'est pas que de la recherche scientifique, je voudrais saluer tous ceux avec qui j'ai partagé des discussions sport, nutrition et bien d'autres encore. La principale question non élucidée reste de savoir si la thèse c'est paléo ! Enfin mes pensées vont à mes proches sans qui je ne serai, bien sûr, jamais arrivé là. Je pense à mes parents, mes frère et soeur et tout particulièremnt à ma tendre Lavi avec qui j'ai le plaisir de partager ma vie.

Résumé en français

Introduction

Contexte

Cette thèse s'inscrit dans le cadre de la Chaire de cyberdéfense des systèmes navals 1 . Fondée en 2014 autour de deux partenaires académiques Télécom Bretagne (aujourd'hui IMT Atlantique) et l'École Navale ainsi que deux partenaires industriels Thales et DCNS (aujourd'hui Naval Group), elle a pour objectif d'organiser un effort de recherche sur les problèmes de cyberdéfense dans l'environnement naval, d'abord militaire mais aussi civil. Nous sommes plusieurs doctorants à travailler sur des sujets de cyberprotection, cyberdéfense et cyberrésilience. Mon sujet plus particulièrement s'intéresse à la protection des données.

Organisation

L'objet de cette thèse est d'étudier dans quelles mesures la cryptographie homomorphe pourrait être utilisée à bord des navires. Celle-ci permettant l'utilisation de données chiffrées dans un programme, cela consisterait en un obstacle supplémentaire pour un attaquant souhaitant voler des données opérationnelles. Étant donné le dynamisme de ce sujet au sein de la communauté cryptographique, nous avons focalisé notre attention sur trois sujets principaux, qui seront repris dans leur ordre de traitement chronologique dans ce manuscrit.

• D'abord, nous avons endossé un rôle d'attaquant afin d'avoir une bonne compréhension des façons de casser cette cryptographie. Cela nous a conduit à imaginer une nouvelle attaque, reposant sur des résultats existants, mais dans un cadre plus ciblé permettant d'améliorer l'état de l'art. Ce résultat a fait l'objet d'une publication à IndoCrypt 2017 (chapitre 3). Ce travail nous a permis de rejoindre la communauté de cryptanalyse algorithmique autour notamment du développement de la bibliothèque de fonctions fplll (chapitre 4).

• Avec la maîtrise du volet attaque, nous avons donc décidé de faire un état de l'art des schémas homomorphes existants et de les comparer. Ce travail, effectué avec Vincent Migliore, a vocation à faciliter le travail aux implémenteurs, pas nécessairement cryptographes, en leur fournissant notamment des tables de paramètres (sûrs et corrects) précalculées, adressant de multiples cas d'usages (chapitre 5).

• Enfin, lors d'un stage doctoral au CWI à Amsterdam, nous avons travaillé avec Léo Ducas et Max Fillinger à la construction et implémentation d'un nouveau schéma de chiffrement homomorphe, généralisant un schéma existant en lui apportant de multiples améliorations (chapitre 6).

Nous invitons le lecteur à parcourir le chapitre 2 pour les quelques notations et définitions qui pourraient être nécessaires à la lecture de ce résumé.

Présentation de la cryptographie homomorphe

Imaginée en 1978 [START_REF] Ronald L Rivest | On data banks and privacy homomorphisms[END_REF], la cryptographie complètement homomorphe n'a été réalisée pour la première fois qu'en 2009 par les travaux de Gentry [START_REF] Gentry | Fully homomorphic encryption using ideal lattices[END_REF]. Cette cryptographie a pour but de permettre la réalisation de traitement sur des données chiffrées de telle façon que le résultat puisse être déchiffré et soit identique au résultat qui aurait été obtenu si ce traitement avait eu lieu sur les mêmes données non chiffrées. C'est le caractère homomorphe du traitement. Depuis 2009, de nombreux schémas homomorphes ont vu le jour, améliorant les performances ou réduisant les hypothèses nécessaires à leurs sécurités. Une première famille de schémas repose sur l'utilisation d'entiers [START_REF] Van Dijk | Fully homomorphic encryption over the integers[END_REF][START_REF] Coron | Fully homomorphic encryption over the integers with shorter public keys[END_REF][START_REF] Coron | Public key compression and modulus switching for fully homomorphic encryption over the integers[END_REF], une autre, plus prometteuse, sur des réseaux euclidiens (lattices en anglais) [BV11b, BGV12, FV12, BLLN13]. Tous ces schémas constituent la deuxième génération. C'est la plus mature et ses performances sont très intéressantes, nous avons donc commencé notre travail avec ses schémas. Ensuite [START_REF] Gentry | Homomorphic encryption from learning with errors: Conceptually-simpler, asymptotically-faster, attributebased[END_REF][START_REF] Khedr | SHIELD: scalable homomorphic implementation of encrypted data-classifiers[END_REF] ont introduit une troisième génération de schémas et enfin, les propositions les plus récentes apparues au cours de cette thèse [DM15, [START_REF] Chillotti | Faster fully homomorphic encryption: Bootstrapping in less than 0.1 seconds[END_REF][START_REF] Chillotti | Faster packed homomorphic operations and efficient circuit bootstrapping for TFHE[END_REF] forment ce que nous pouvons appeler la quatrième génération. Notre travail au CWI s'inclut dans cette dernière vague.

Un exemple : le schéma de Fan-Vercauteren

Introduit en 2012 comme une généralisation sur anneaux du schéma [START_REF] Brakerski | Fully homomorphic encryption without modulus switching from classical GapSVP[END_REF], le schéma de Fan et Vercauteren [START_REF] Fan | Somewhat practical fully homomorphic encryption[END_REF], que nous appellerons FV, a rencontré beaucoup de succès. C'est notamment le schéma choisi par Microsoft Research pour leur bibliothèque de fonctions [START_REF] Laine | Simple Encrypted Arithmetic Library -SEAL v2.3[END_REF]. On retrouve également une implémentation de FV sur NFLlib [Cry]. Simple à énoncer et reprenant les principaux éléments de sa génération, c'est ce schéma qui nous a servi comme porte d'entrée, pour notre travail de cryptanalyse notamment.

Le schéma. Pour la description de FV nous avons besoin d'un anneau R de dimension n. Pour une exposition facile, le choix est souvent fait de définir R = Z[x]/(f (x)) où f (x) = x n + 1 est un polynôme cyclotomique et donc n une puissance 2. De plus nous restreignons à R q , l'anneau composé des éléments de R aux coefficients dans ]q/2, q/2] pour un module q fixé.

• Génération de clés : La clé secrète s k est un élément de R q , généralement petit. La clé publique est p k ∈ R 2 q définie par : p k = (p 0 , p 1 ) = (-(a • s + e) mod q, a)

où s est la clé secrète, a et e sont tirés aléatoirement, uniformément dans R q pour a et selon une gaussienne discrète d'écart type σ dans R pour e.

• Chiffrement : l'ensemble des clairs est l'anneau R t pour un entier t ≥ 2. Le chiffrement d'un message m ∈ R t se réalise comme suit :

c = (c 0 , c 1 ) = (�q/t� • m + p 0 • u + e 1 , p 1 • u + e 2 )
où u est tiré aléatoirement uniforme dans R 2 et e 1 , e 2 sont tirés selon une gaussienne d'écart type σ dans R.

• Pour déchiffrer, il suffit de calculer �(c 0 + c 1 • s) × t/q� pour retrouver m.

La partie intéressante est donc comment les opérations se déroulent sur les chiffrés. Donnons nous c a et c b des chiffrés de m a et m b .

• L'addition se fait simplement terme à terme

c + = (c 0 + , c 1 + ) = (c 0 a + c 0 b , c 1 a + c 1 b ) ∈ R 2 q
Il est aisé de vérifier qu'il s'agit bien d'un chiffré de m a + m b .

• La multiplication est un peu plus complexe puisque l'analogue à l'addition terme à terme, fait apparaître une troisième terme. Il est donc nécessaire de réaliser une opération de relinéarisation afin de retrouver un chiffré valide. Cette relinéarisation, nécessite du matériel de clés supplémentaire, en plus de la clé publique, que l'on nomme simplement clé de relinéarisation.

Grâce à cette brève présentation, on peut noter que FV est paramétré par différentes variables : l'anneau R, sa dimension n, un module q et un écart type pour l'erreur σ. Il en est de même pour la plupart des schémas homomorphes et même plus largement de la cryptographie à base de réseaux euclidiens.

Conception d'une nouvelle attaque

Notre premier travail de recherche a consisté à faire l'état des lieux des attaques possibles contre les schémas de chiffrement homomorphe afin de déduire par la suite des paramètres sûrs pour une utilisation maîtrisée. Le problème difficile principal sur lequel repose la plupart des solutions cryptographiques sur les réseaux euclidiens est le problème Learning with Errors ou LWE [START_REF] Regev | On lattices, learning with errors, random linear codes, and cryptography[END_REF]. Celui a pour but d'apprendre un secret masqué au milieu d'équations linéaires bruitées. Plus précisément, étant donné une dimension n, un module q et une distribution de probabilités χ d'écart type σ, fixons s = (s 1 , ..., s n ) et construisons m couples de la façon suivante :

(a i , �a i • s� + e i mod q)

où chaque a i et e i sont constitués de n coordonnées tirées uniformément aléatoires pour a i et selon la distribution de probabilités χ pour e i . Ces m échantillons sont rendus publics et deux problèmes en découlent : Decision-LWE (décider si ces m échantillons ont été construits ainsi ou de façon complètement aléatoire) et Search-LWE (retrouver s). Un problème similaire a été défini avec des anneaux, Ring-LWE [START_REF] Lyubashevsky | On ideal lattices and learning with errors over rings[END_REF] pour lequel il existe également une variante décisionnelle et une variante recherche. Il a été démontré de nombreux résultats garantissant que ces problèmes sont difficiles asymptotiquement. Il reste donc à estimer leurs difficultés concrètes étant donné un jeu de paramètres (n, q, σ) fixé. Pour cela, il convient d'analyser les performances des différentes méthodes de résolution de ces problèmes.

Juste avant le début de cette thèse, Albrecht et al. ont réalisé une excellente synthèse pour LWE [START_REF] Martin R Albrecht | On the concrete hardness of learning with errors[END_REF]. Plus tard Peikert en a également réalisé une pour Ring-LWE [START_REF] Peikert | How (not) to instantiate ring-LWE[END_REF]. En nous appuyant sur ces travaux, nous avons pu nous intéresser de plus près aux performances de ces attaques sur des instances avec des paramètres propres à la cryptographie homomorphe. En effet toutes ces attaques sont génériques, or comme nous le verrons par la suite en détails, le caractère homomorphe impose des contraintes sur le triplet (n, q, σ) qui pourraient être mises à profit par un attaquant.

La nouvelle attaque

Profitant d'une erreur petite et d'un module trÈs grand, nous avons composé une attaque en suivant le modèle de celle de Bai et Galbraith [START_REF] Bai | Lattice decoding attacks on binary LWE[END_REF]. Ces résultats ont été présentés lors de la conférence IndoCrypt 2017.

Plongement. Notre montage diffère sur quelques points. Le plongement n'est pas réalisé exactement de la même façon. Nous le réalisons de la façon suivante

B = � I n -A 0 qI n � ∈ Z 2n×2n
Alors que Bai et Galbraith le font comme suit

M = � I n -A qI 2n � ∈ Z 3n×2n
devant ensuite en calculer la forme normale de Hermite pour obtenir une matrice de rang complet. Notre solution est donc sensiblement plus efficace et nous donne une base très particulière (triangulaire supérieure, par bloc, avec l'identité sur la diagonale à un facteur près). Cette forme particulière s'avère en effet utile pour l'étape suivante de l'attaque : la recherche de vecteur le plus proche.

Réduction de réseaux. Une recherche de vecteur le plus proche passe nécessairement par une phase de réduction du réseau concerné afin que la base soit favorable à la recherche effective. Plusieurs algorithmes s'offrent à nous pour cette opération : LLL [START_REF] Klaas Lenstra | Factoring polynomials with rational coefficients[END_REF] de faible complexité mais dont la qualité de réduction est moyenne ou BKZ [START_REF] Schnorr | Lattice basis reduction: Improved practical algorithms and solving subset sum problems[END_REF] moins rapide mais produisant des bases de meilleure qualité. Nous avons analysé lequel de ces algorithmes est le plus pertinent pour notre cas ainsi que les meilleurs paramètres à lui définir. Il s'est avéré qu'un LLL faible, donc très rapide, nous permettait de réussir nos attaques.

Énumeration. Une fois la base réduite, plusieurs algorithmes existent pour réaliser une recherche de vecteur proche. Nous avons opté pour l'énumération [START_REF] Liu | Solving BDD by enumeration: An update[END_REF]. Cette méthode est la meilleure pour les instances accessibles aujourd'hui mais nous savons que les méthodes de crible sont plus performantes asymptotiquement et pourraient le devenir aussi en pratique [START_REF] Herold | Improved algorithms for the approximate k-list problem in euclidean norm[END_REF].

Expériences réelles

Après avoir assemblé de façon théorique les différents éléments de cette attaque, nous en avons réalisé une implémentation pour étudier ses performances pratiques. Notre cible d'attaque a été l'implémentation de Lepoint [START_REF] Lepoint | A proof-of-concept implementation of the homomorphic evaluation of SIMON using FV and YASHE leveled homomorphic cryptosystems[END_REF]. Si nous devions faire les mêmes expériences aujourd'hui, notre choix porterait sur la bibliothèque SEAL [START_REF] Laine | Simple Encrypted Arithmetic Library -SEAL v2.3[END_REF] qui, elle, a vocation à être réellement utilisée. Pour l'attaque, nous avons utilisé la bibliothèque fplll [dt17] pour la réduction des réseaux. Le reste a été implémenté par nos soins. Par la suite nous avons découvert que fplll avait également du code « expérimental » pour l'énumération avec lequel nous avons travaillé par la suite.

Résultats. Ces expériences, lancées contre des centaines d'instances de FV avec différents paramètres de dimension, module et erreur nous ont d'abord amenés à considérer la réduction de réseaux. En effet, dans l'idéal les efforts fournis sur la réduction doivent être équilibrés par rapport à ceux fournis sur l'énumération. Or il s'avère qu'avec nos premiers choix (BKZ notamment), la quasi-totalité du temps était passée sur la réduction. Nous avons donc évolué petit à petit vers une réduction de plus en plus faible jusqu'à un faible LLL (η = 0.71). La partie énumération, quant à elle, resta très rapide également. De façon surprenante, nous n'avions nul besoin d'énumérer puisque le premier candidat (la solution de Babai [START_REF] Babai | On Lovász'lattice reduction and the nearest lattice point problem[END_REF]) était presque toujours celle que nous cherchions.

Nous avions donc entre les mains une attaque composée uniquement de procédures aux coûts polynomiaux en temps. Cela aurait pu être un vrai problème pour la cryptographie homomorphe. Toutefois, après avoir longuement approfondi l'analyse du comportement de notre attaque, nous avons établi que celle-ci ne passerait pas à l'échelle et n'inquièterait pas des instances proposant 80 bits de sécurité par exemple.

Bien que les retombés de notre travail soit limité, la communauté l'a suivi de très prêt, puisque c'était un des premiers de ce genre. L'an dernier Albrecht [START_REF] Albrecht | On dual lattice attacks against small-secret LWE and parameter choices in HElib and SEAL[END_REF] a présenté un travail similaire aux résultats plus forts.

Contribution en réduction de réseaux

Du fait de notre investissement sur le sujet de la réduction de réseaux pour la compréhension de notre attaque, nous avons rejoint la communauté gravitant autour du projet fplll [dt17], notamment lors de rencontres de programmation : les fplll days. Ces évènements réunissent deux fois par an les intéressés pour faire avancer le projet : ajout de fonctionnalités, optimisation, documentation... Nous avons donc pu apporter notre concours à ce projet à ces occasions.

Améliorer la recherche de proches vecteurs. Réel besoin pour notre attaque, cette fonction que nous avions découverte par hasard n'était pas recommandée à l'usage. Nous avons donc consacré du temps à la rendre correcte. Ces problèmes étaient déjà évoqués par Pujol [START_REF] Pujol | Recherche efficace de vecteur court dans un réseau euclidien[END_REF]. BKZ 3. Un grand nombre d'heuristiques ont été proposées pour améliorer les performances de BKZ en pratique. Elles ont été regroupées sous le nom de BKZ 2.0 [START_REF] Chen | BKZ 2.0: Better lattice security estimates[END_REF]. Ces résultats ayant déjà quelques années, nous avons travaillé à plusieurs lors des journées fplll pour tester de nouvelles heuristiques et ouvrir le chemin vers un futur « BKZ 3.0 ». De multiples techniques ont été mises à l'épreuve, certaines déjà intégrées d'autres pas encore. Il est encore trop tôt pour réaliser une publication.

LLL en deux phases. Phénomène déjà constaté auparavant, nous avons pu mettre en évidence lors de nos multiples expériences avec l'algorithme LLL, qu'il était souvent plus rapides de le réaliser en plusieurs passes, avec des paramètres moins exigeants que ceux souhaités en tant que pré-calculs. Il ne s'agit pas d'une vérité universelle mais les gains que nous avons ne sont pas négligeables. Aussi il est intéressant d'en faire l'expérience lors de réduction de réseaux avec ces propriétés.

Choix de l'algorithme et des paramètres

Forts de ces expériences en cryptanalyse, nous avons pu nous tourner avec confiance vers la tâche suivante, celle du choix du meilleur cryptosystème homomorphe et de ses paramètres. En commun avec Vincent Migliore, nous avons donc effectué cette étude comparative dans le but de fournir un contenu d'accès facile pour les implémenteurs. Ce travail a été accepté pour un numéro spécial des Transactions on Computers de l'IEEE sur « l'ingénierie cryptographique dans le contexte post-quantique » [?].

Périmètre de l'étude

Ce travail débuté à l'été 2016 nous avons d'abord considéré les schémas les plus prometteurs à cette époque, c'est-à-dire YASHE' [START_REF] Joppe W Bos | Improved Security for a Ring-Based Fully Homomorphic Encryption Scheme[END_REF], FV [START_REF] Fan | Somewhat practical fully homomorphic encryption[END_REF] de deuxième génération ainsi que SHIELD (ou Ring-GSW) [START_REF] Khedr | SHIELD: scalable homomorphic implementation of encrypted data-classifiers[END_REF] et F-NTRU [START_REF] Doröz | Flattening NTRU for evaluation key free homomorphic encryption[END_REF] de troisième génération. Plus tard, suite à différentes attaques [START_REF] Albrecht | A subfield lattice attack on overstretched NTRU assumptions -cryptanalysis of some FHE and graded encoding schemes[END_REF][START_REF] Kirchner | Revisiting lattice attacks on overstretched NTRU parameters[END_REF], nous avons dû retirer YASHE' et F-NTRU qui n'était plus viable. Notre étude permet néanmoins de mettre en regard des schémas de deuxième et troisième génération sur des cas très concrets.

Nous nous sommes ensuite donnés plusieurs cas d'usages afin de mettre en évidence les avantages et inconvénients des schémas selon les situations. Il en découle de nombreuses tables de paramètres. Les valeurs des paramètres permettent ensuite de se faire un avis sur le coût d'utilisation de chacun des schémas. En effet les tailles de clés ou chiffrés en dépendent directement, tout comme les temps de calcul, eux aussi liés à la taille des données manipulées.

Réalisations

Pour réaliser cette étude nous avons donc remis les schémas sous un formalisme commun, afin d'en dériver des équations de fonctionnement comparables. Calculer les paramètres revient donc à trouver les valeurs qui satisfont à la fois ces équations de fonctionnement et les conditions de sécurité.

Pour ce faire, nous avons donc réalisés un script de recherche. Celui-ci inclus les équations de fonctionnement des schémas et s'interface avec l'estimateur de sécurité de Albrecht [Albb]. Celui-ci étant toujours mis à jour à mesure que de nouvelles techniques d'attaques sont publiées il nous paraissait important de pouvoir maintenir nos tables à jour facilement.

Résultats

Chaque situation mérite une attention particulière, néanmoins plusieurs tendances se dégagent de l'ensemble de nos résultats.

1. Pour des petites profondeurs multiplicatives, FV présente de plus petits paramètres, alors que si le circuit à évaluer le permet SHIELD sera meilleur pour des profondeurs supérieures. Le changement a lieu autour d'une profondeur 8.

2.

Dans le cas où du batching serait possible ou souhaité, FV est généralement meilleur que SHIELD. Le batching consiste à évaluer un même circuit sur plusieurs données en même temps, grâce à un empaquetage de plusieurs clairs dans un chiffré unique.

Ce travail a comporté de nombreux challenges, se tenir à l'état de l'art en est un. Il est également difficile de comparer des schémas dont les structures ne comportent que peu de points communs. Notre travail est un des premiers du genre et appelle à être prolongé par une comparaison des performances réelles des schémas. Plusieurs sont déjà implémentés au sein de bibliothèques de fonctions open-source (Helib, SEAL, ...). Nous avons également initié l'implémentation de SHIELD en utilisant NFLlib pour permettre une comparaison la plus simple possible dans un travail futur.

Construction d'un nouveau schéma

La dernière contribution principale de cette thèse s'attèle à être force de proposition dans la dynamique communautaire de cryptographie homomorphe. Après avoir éprouvé la sécurité des schémas existants et comparé deux des propositions les plus prometteuses, nous avons travaillé à la conception et implémentation d'un schéma de dernière génération. Cette contribution est le fruit de mon séjour de recherche au sein du CWI d'Amsterdam. Dans cette collaboration avec Léo Ducas et Max Fillinger, j'ai assuré la partie design et réalisation de l'implémentation de ce schéma.

Un schéma de quatrième génération

Issue des travaux initiés par FHEW [START_REF] Ducas | FHEW: Bootstrapping homomorphic encryption in less than a second[END_REF], la dernière génération des schémas complètement homomorphes apporte un profond changement de paradigme. Avant les dimensions du circuit à évaluer jouait un rôle prédominant dans le choix des paramètres des schémas. En effet le « bruit » intrinsèque aux chiffrés augmentant au cours de l'évaluation, il est nécessaire de choisir les paramètres pour que ce bruit n'empêche pas un déchiffrement correct. Or les schémas de quatrième génération ont pour caractéristique principale de maintenir un niveau de bruit constant au cours de l'évaluation du circuit. Cette dernière génération est encore très jeune et de nombreuses améliorations théoriques sont possibles. Notre travail est une extension de FHEW, orthogonal à celle proposée par [START_REF] Chillotti | Faster fully homomorphic encryption: Bootstrapping in less than 0.1 seconds[END_REF][START_REF] Chillotti | Faster packed homomorphic operations and efficient circuit bootstrapping for TFHE[END_REF].

L'évolution principale introduite dans ce schéma est l'utilisation de deux accumulateurs homomorphes dans deux anneaux de dimension modérée. Puis, grâce un produit tensoriel avant l'extraction de fonction, il est possible de rétablir une grande expressivité, tout en maintenant des coûts globaux très modestes. L'implémentation que nous discutons ci-dessous permet de réaliser des évaluations de portes logiques binaires sur 6 bits d'entrée en 6 secondes. La structure du schéma est présenté dans la figure 1.

De nombreux challenges pour l'implémentation

La figure 1 illustre bien l'hétérogénéité des objets à manipuler pour réaliser la porte dans sa globalité. Mes trois mois passés au CWI ont été dédié à réaliser une meilleure implémentation possible du schéma afin qu'il soit facilement évolutif (donc compréhensible par une personne extérieure) mais aussi performant pour révéler tout le potentiel des idées théoriques.

La réalisation a donc été faite en C++11 et l'usage de templates est la principale technique utilisée pour répondre aux objectifs de modularité et de performances. Des routines de bas-niveau ont été implémentés pour l'arithmétique modulaire et la manipulation d'éléments d'anneaux omniprésentes. Ensuite les objets cryptographiques en font usage.

Seules les transformés de Fourier, nécessaires aux multiplications d'éléments d'anneaux, sont réalisés par une bibliothèque externe, FFTW. Celle-ci nous a d'ailleurs apporté une contrainte de stabilité numérique. Étant donné que les transformés ont lieu sur des nombres à virgule flottante en double précision (i.e. 53 bits de mantisse), nous devons nous assurer que nos calculs ne dépassent jamais ce seuil. Le risque serait de faire apparaître une erreur supplémentaire dans le cryptosystème. Comme nos valeurs de modules pour l'arithmétique modulaire peuvent atteindre de très grandes valeurs (jusqu'à 2 56 ), nous devons dans ces cas scinder les éléments d'anneaux en leur partie de poids fort et celle de poids faible, procéder aux transformés sur chaque moitié et réaliser des multiplications terme à terme correctement (à la Karatsuba).

Performances

Notre première implémentation fonctionne pour 6 bits d'entrée avec les performances suivantes :

• Temps de génération de clés (une fois par programme) : 38 secondes ;

LWE t|pq s (m) c = (a, b) • mod p • mod q (a (p) , b (p) ) (a (q) , b (q) ) ExtExpInner ExtExpInner R p LWE t|Q sp � X b-�a,s� mod p � ModSwitch Q→Q⊗ R p GSW t|Q sp (X s i ) KS ψα(sp)→sp R q LWE t|Q sq � Y b-�a,s� mod q � ModSwitch Q→Q⊗ R q GSW t|Q sq (Y s i ) KS ψα(sq)→sq � ModSwitch Q⊗→Q � R pq LWE t|Q � spq � Z b-�a,s� mod pq � FunExpExtract f (� • �t:pq) LWE t|Q � s (f (m)) KS spq→s � , KS s � →s ModSwitch Q � →pq � m = � γ i m i • • • ×γ 1 ×γ 2 ×γ k LWE t|Q � s (m 1 ) LWE t|Q � s (m 2 ) LWE t|Q � s (m k ) a (p) 1 a (p) 2 a (p) 3 . . . b (p) a (q) 1 a (q) 2 a (q) 3 . . . b (q) N f L c
Sur la partie gauche, on voit les k bits d'entrée m 1 , • • Temps d'évaluation d'une porte : 6.4 secondes ;

• Consommation mémoire : 9.2 Gio.

Le temps de la porte se décompose en 0.60 s pour chaque accumulateur (qui pourraient être calculés en parallèle), 4 s pour un changement de clés dans l'extraction de fonction, et 0.55 s pour les opérations liés au bit de sortie. Il serait donc possible de réaliser une fonction binaire de 6 bits vers 6 bits en une dizaine de secondes.

The Chair of Naval Cyber Defence

This thesis work is an integral part of the overall research effort conducted within the Chair of Naval Cyber Defence 1 . This industrial chair has been launched in 2014 as a partnership between academic institutions and industrial players of the defense sector. Thales Group and Naval Group (formerly DCNS) are joined by the Institut Mines-Télécom Atlantique (formerly Télécom Bretagne) and the French Naval Research Institute and together they cover all scientific, academic and applications aspects. The motivation for this chair is to have a scientific approach to bring new solutions for improving cybersecurity on military ships. Cyber-security is usually divided into cyber-protection, cyber-resilience and cyberdefense. The chair consists in several doctoral and post-doctoral students whose works cover this whole spectrum. The present work is about cyber-protection and the target application of this thesis is to secure data aboard ships, military ships as a first motive but commercial ships as well.

A walk through the history of cryptology

What can crypto do for you?

Cryptology, from the Greek κρνπτ oς (secret) and λoγια (science) is the study of means to protect information (to use only broad terms). It is the union of cryptography (the creative, constructive part) and cryptanalysis (the assessment, attack counter-part). The first example of cryptography in history is the Caesar cipher, used by Emperor Julius Caesar during his conquests, more than two thousands years ago. The cryptanalytic technique that breaks this cipher is called frequency analysis and dates back from the 9th Century with Al-Kindi's work. Since these times, cryptologic work has been a cat-and-mouse game where cryptographers build more and more clever ways to protect information that cryptanalysts aim at breaking.

The overall protection objective is usually partitioned into three sub-objectives whose acronym C.I.A. is easy to remember. C stands for confidentiality: we do not want an eavesdropper to get the content of a protected exchange, I for integrity: the communication should not be altered by errors or attacks, and A for availability, legitimate entities should be able to access the information. In cryptology we call primitives the elementary building blocks that together form a complete protection solution. We refer here loosely about entities or eavesdropper, we shall in this work use the term user(s) when talking about the legitimate participants and attacker for the malicious, adverse party whose aim is to break the protection to some extent.

From an application viewpoint, we wish to limit the extra costs induced by the cryptographic protection to the minimum. As we shall see in this work, this is not always a trivial objective.

From paper-and-pencil to quantum... and post-quantum!

Let us now quickly review the last two thousands years of outstanding advances in cryptology. The paper-and-pencil area spans from Caesar cipher to the German AFDX cipher of the First World War. Depending on the technique, we speak about code or cipher. The former is about replacing meaningful word by others that only the legitimate recipient can understand, while the latter is about modifying the message content into something scrambled using substitution or mixing. A famous example of a code is Verlaine's poem Les sanglots longs des violons de l'automne that was broadcast by the BBC to French resistant forces during the Second World War. When the next verse was added Blessent mon coeur d'une langleur monotone, the message yields: "This is D-Day!". The Caesar cipher is an example of substitution, each letter is replaced by the one three position after in the alphabet: A becomes D, B becomes E and so on. So "This is D-Day" would be ciphered as WKLV LV G-GDB. Another example of cipher, using mixing only, say swap two consecutive letters in the message, would change our message into "HTSI SI D-DYA".

Of course none of these toy techniques are secure by today's standards, yet they have been state-of-the-art in their times. The Caesar cipher is called a mono-alphabetical substitution because encryption is about taking a letter replacement from one unique alphabet (the regular alphabet shifted by three in our example above). Another famous cipher of that kind is called Polybe Square which is about putting all the letters into a square and replacing them by the pair (row number, column number). These techniques were only broken by Al-Kindi's work on frequency analysis in the 9th Century when he realised that the most frequent letter in the original text remains the most frequent letter (or number) in the ciphertext. Thus, if you know the original text language you can easily decrypt the message. After mono-alphabetical substitution, Vigenère introduced the poly-alphabetical cipher: the Vigenère cipher. This time, the letters of the message are not shifted by the same number of positions, but by a changing number of positions. For example the first would be shifted by eight positions, the second by twelve positions, the third by five, and the next by eight again and you loop like this for the whole message. This way, two identical letters in the ciphertext are not necessary the same in the cleartext. Analysing frequencies becomes more difficult. Now the attacker shall consider statistics on one every n letters in the ciphertext. Indeed in our example, every third letter is shifted by the same number of positions (eight, twelve or five). The first challenge is to find the number of shifts (i.e. the length of the key) before doing frequency analysis. The extreme version of this poly-alphabetical cipher, when each letter is shifted by an unpredictable number of positions (no loops and randomness), is called Vernam Cipher and is the only perfectly secure cipher ever to be built. Indeed this is perfectly secure as demonstrated by Shannon in his seminal work on information theory. The drawback of this cipher is that the key (the shifts to apply) is as long as the message, doubling the cost or time of the communications. Another famous cryptographic proposal from the pencil-and-paper time is the AFDX, later ADFVX cipher. It is similar to the Polybe Square in that you write the letters in a 5 × 5 or 6 × 6 square whose columns and rows do not bear numbers but letters (A, F, D, X and V). To encrypt you apply this substitution, followed by a mixing operation on the resulting letters. This cipher was famously used in the First World War by the Germans and broken by the French George Painvain, only with pencil and paper. The last famous cryptosystem to mention from the pre-computer area is the Enigma machine, again an extraordinary invention from the Germans that gave many troubles to the Allies. This mechanical device used rotors and wiring to apply a poly-alphabetical substitution to the messages and was not broken in the cryptographic sense. Indeed what was successfully used to recover messages was the brute-force technique that attempts every possible key against ciphertexts whose clear content was partially known. This brute-force attack was made possible by the Bombe of Alan Turing.

Later on, the development of communication devices and computers increased the need for information protection and provided new capabilities to protect. . . and to attack. The major problem of the techniques above is that they do not scale easily to world-wide communication. In all of them, the users have to share a piece of secret information (shifts, rotor configurations. . . ), that we generally call the secret key. This means that, prior to any communication, there must have been a key exchange between the users. For military or highly critical communications, it is worth paying someone to physically deliver some key materials (think about a carrier handcuffed to a locked suitcase for example) to support some amount of communication. But that cannot apply to private companies or individuals that would want to engage in secure communications. The solution to this was brought by Diffie and Hellman in 1976 (it was also invented by Cocks, from the British Intelligence Service, but the information was declassified only in 1997). The key exchange protocol allows two users to establish a common secret, using only public information exchanges. The first cryptosystem by Rivest, Shamir and Adleman (RSA) in 1978 provides another solution: it uses one public key to encrypt and another private to decrypt. Like this, everybody can encrypt a message to someone, who will be the only one able to retrieve the content. This is called asymmetric cryptography as opposed to symmetric cryptography. This marks the beginning of modern cryptography.

Today, cryptography provides many different primitives: symmetric encryption, asymmetric encryption, signature, key exchange, zero knowledge, random number generation... There are several standardised algorithms for these building blocks and, following the principles from Kerckhoffs, their design has been publicly reviewed and assessed by cryptographic experts for some time before being widely deployed. These proposals provide security proofs. Some are information theoretical results, some are hardness reductions to problems known or proven to be hard. The cryptosystem RSA, for instance, is believed secure because it somehow relates to the problem of factoring big integers, which has been a target from number theorists for centuries. Hence, it is assumed that no one will come up with an unexpectedly efficient algorithm to solve it. Thus, breaking RSA should be difficult. Hence most cryptographic components today rely on few of such hard problems to ensure security. The problems are: integer factorisation, discrete logarithm in cyclic groups. The only 100% proven secure algorithm is the Vernam cipher, also referred to as the One-time pad. However, the ground-breaking result from Shor in 1994 came shaking the status-quo. His contribution known as Shor's algorithm is an efficient algorithm that works against both the discrete logarithm and the factorisation problem. . . but requires a quantum computer to work. Therefore we stand today with the knowledge that all deployed cryptographic components could be broken the day when a quantum computer is up and running Shor's algorithm. This is why, we see the emergence of post-quantum cryptography, meaning resistant to quantum attackers. It should not be mixed up with quantum cryptography which uses quantum properties to achieve security, for example quantum entanglement can be used to perform perfectly secure key exchange. This post-quantum cryptography has now been under study for several years, with first steps in 1978 with McEliece or 1996 with Ajtai. The U.S. National Institute of Standards and Technology (NIST) has annonced in 2015 a call for proposals of quantum resistant primitives, like it did in the past for other primitives, mostly with success. Cryptographers turn to different mathematical objects in order to achieve quantum resistance, lattices are among them. In addition, lattices allow to build more advanced primitives such as homomorphic encryption. This kind of cryptography had been conjectured in 1978 but only realised in its full version, with lattices, in 2009 by Gentry. Homomorphic encryption is about encrypting data in such way that, once encrypted, they can still be operated upon. And when you decrypt the result of the computation, it yields the same result as if the computation had been done on the un-encrypted data. It was originally called privacy homomorphism because it allows users to have their data being used by a third-parties (e.g. service provider) while keeping their data private. In a context of medical sensors or external storage and services (aka cloud), this cryptographic feature brings timely solutions.

This thesis

Outline

Fully Homomorphic Encryption (FHE) is therefore today a trendy topic, with high expectancies put into it, attracting much attention in the cryptology community. The aims of the present work is to participate in the effort to make FHE practical and study the added value such cryptography could bring to secure information aboard military ships. Because of the pace of FHE improvements, the overall context has been moving quite a lot between the beginning and the end of this work. Nevertheless, we have conducted our study to the end. The approach we had was the following. First, we reviewed the most promising proposals, aiming first at understanding their security. Indeed the foundations of lattice-based cryptography are quite young, in cryptographic scale. Several years are usually needed for hardness assumptions to be thoroughly assessed. We contributed to this cryptanalytic effort, with a focus on lattice instances below FHE and lattice reduction. Next, we maintained a technological watch and performed a comparison of the best candidates as of end of 2016, with complete analysis of the costs and settings of each candidate, with real use cases in mind. Finally, we had the opportunity to work on the latest type of FHE scheme and developed a new FHE scheme, improving upon the state-of-the-art and provided a proof-of-concept implementation.

Roadmap

This manuscript follows to some extent the chronological order of the work of these last years.

• First in Chapter 2, we shall set the definitions and notation for the lattice theory we use in this work, together with a formal description of homomorphic encryption.

• Then we will start with our cryptanalysis efforts. Reviewing the state-of-the-art of lattice attacks, we shall present our special-purpose attack in Chapter 3. This work led to a publication in IndoCrypt 2017 [START_REF] Bonnoron | A note on ring-lwe security in the case of fully homomorphic encryption[END_REF]. Then in Chapter 4, as key component, we shall focus on lattice reduction, whose performance is directly linked to the attacker's advantage, and to which we contributed especially with involvements in the development of an open-source library fplll, which is included in Sage.

• Next, we move to our experience on choosing secure parameters for FHE in Chapter 5. We conducted a comparative study of the most promising schemes. Aiming at families of use-cases, we derived the concrete parameters of the schemes. We could then compare them depending on the scenario and provide guidance to the community of implementers on how to correctly setup the cryptography in their designs.

Notation

In the thesis, we use the common mathematical sets, N, Z, and R, respectively the natural integers, the integers and the reals. For a real a, we note |a| the absolute value of a and also �a�, �a� and �a� respectively the rounding of a to the nearest integer smaller than a, bigger than a, and closest to a. For a positive integer q > 0 we denote Z q the set of integers (-�q/2�, . . . , �q/2�].

CHAPTER 2. PRELIMINARIES

Our log function is the logarithm in base 2.

For n > 0 integer, the matrix I n refers to the identity matrix of size n. Capital bold letters are used for matrices, e.g. B, and small ones for vectors, e.g. v. We similarly write B for a matrix or for the ordered family of (row) vectors B = (b 1 , b 2 , . . . , b n ) using bold subscripts. For a vector v, we refer to its components with italic letters v i . We use �•, •� to speak about the inner product of two vectors of the same size.

For a vector v = (v 1 , . . . , v n ) ∈ R n , we define the Euclidean norm and note �v� 2 = � � n i=1 v 2 i , and the infinity norm �v� ∞ = max 1≤i≤n |v i |. We may omit the subscript when it is clear from the context.

Rings

When dealing with a polynomial p of degree n -1, we use the coefficient embedding (unless specified) and assimilate it as a coordinate vector: p = (p 0 , p 2 , . . . , p n-1 ). We will work with polynomials in a polynomial ring R = Z[x]/(f (x)) for some f ∈ Z[x]. We denote R q the set of polynomials in R with coefficients in Z q .

For a ∈ R (or R q ) we define two norms:

• The Coefficient norm as �a� = �(a 0 , . . . , a n-1 )� = � � n-1 i=0 a 2 i .
• The Operator norm as |a| = max b∈R\{0} �ab�/�b�. We expand this notion to vectors x ∈ R m with m > 1 by maximizing y over R m \ {0} and replacing the multiplication with the inner product over R.

Random variables

For a ring R and a polynomial a, we say a ← U R when a is sampled uniformly in R, A ← B R when it is sampled with binary coefficients and a ← D R,σ when its coefficients are sampled independently from a (centred) discrete Gaussian distribution with width parameter σ, i.e. proportional to exp(-πx 2 /σ 2 ).

We say that a real random variable X is subgaussian with parameter δ (or δ-subgaussian) if E[X] = 0, and for all t, E[exp(tX)] ≤ exp � t 2 δ 2 /2 � . We consider only centred subgaussian variables (E[X] = 0). Subgaussian random variables have the following well known properties Let X 1 and X 2 be subgaussian random variables with parameters δ 1 and δ 2 , respectively.

• X 1 + X 2 is (δ 1 + δ 2 )-subgaussian. • If X 1 and X 2 are independent, X 1 + X 2 is � δ 2 1 + δ 2 2 -subgaussian.
• aX 1 is (|a|δ 1 )-subgaussian.

• Subgaussian tail estimate:

P (|X 1 | ≥ √ 2λδ 1 ) ≤ 2 exp(-λ).

Gadgets

Throughout this exposition we use a binary decomposition operation on ring elements, and the reverse. For simplicity we adopt the notation of gadget vector and matrix.

The gadget vector g T of size K is set to

� 1 2 2 2 • • • 2 K-1 � ∈ R K d .
Reciprocally, we define g -T as a function such that, for w ∈ R n d , V = g -T (w) is a (K × n)-matrix whose entries are ring elements with coefficients in {0, 1} such that g T V = w.

For some integer n ≥ 1, the gadget matrix G n is defined by

G n = I n+1 ⊗ g ∈ R (n+1)K×(n+1) d . G T n =      1 2 • • • 2 K-1 0 0 • • • 0 • • • 0 0 • • • 0 0 0 • • • 0 1 2 • • • 2 K-1 • • • 0 0 • • • 0 . . . . . . . . . . . . 0 0 • • • 0 0 0 • • • 0 • • • 1 2 • • • 2 K-1      We define G -1 n similarly to g -T : for a ∈ R n+1 d , we let d = G -1 n (a) ∈ R (n+1)K d
be the vector whose entries have coefficients in {0, 1} such that d T • G = a. For convenience we write G n = G as n is typically clear from context.

Some lattice theory

In this section we synthesise the notions about lattices that will be used throughout this thesis.

General definitions

In general, a lattice L of dimension n is a discrete additive subgroup of R n . Integer lattices are discrete additive subgroups of Z n . In this work we only deal with the integer lattices and simply call them lattices.

Lattices (of size n) are usually represented by a basis B, a set of n independent integer vectors (b 1 , b 2 , . . . , b n ) of size n whose integer linear combinations generate the lattice.

L(B) = � n � i=1 v i b i : v i ∈ Z � = � B T v : v ∈ Z n � = BZ n
In our lattices, B is always a square integer matrix, B ∈ Z n×n . For most of the discussion we restrict to this full rank definition and will make it explicit when working with greater generating families of m > n vectors.

For a lattice L, we define its volume Vol(L) as the volume of the fundamental parallelepiped described by the basis vectors,

P 1/2 (L) = { � n i=1 x i b i , |x i | < 1/2}.
This volume is simply the absolute value of the determinant of a basis and is therefore a lattice invariant. We write

Vol(L) = det(L) = | det(B)|
We often use projections onto subsets of basis vectors, so we note π B,i (v), the orthogonal projection of the vector v onto {b 1 , . . . , b i-1 }. Hence π B,1 is the identity.

Given a lattice L we define its dual L � as the set of vectors y ∈ R n such that �x, y� ∈ Z for all x ∈ L. It holds that det(L � ) = 1/ det(L).

q-ary lattices. When studying cryptographic lattice problems, the lattices we mostly work with are called q-ary, because they are defined modulo some integer q (not necessarily prime). These lattices are defined as follows:

L q (B) = � n � i=1 v i b i mod q : v i ∈ Z � = � B T v mod q : v ∈ Z n �
Hence, since we are working modulo q, we can equivalently consider that all the components of B and v are in Z q .

Gram-Schmidt Orthogonalisation (GSO).

We use several times the Gram-Schmidt Orthogonalisation of a basis. This algorithm takes the matrix to orthogonalise B and outputs the resulting matrix B � and a matrix µ (lower triangular with 1 on the diagonal) such that: B = µ × B � . It constructs B � so that its vectors verify:

• b � 1 = b 1 • b � i is the projection of b i orthogonally to the subspace generated by the i-1 first vectors of B. Formally b � i = b i - � i-1 j=1 µ i,j b � j where µ i,j = �b i , b � j �/�b � j , b � j �. We have det(L) = � n i=1 �b � i � 2 .
The algorithm works in polynomial time in the size of the matrix.

Fundamental results

For any lattice, we define Minkowski's successive minima λ i (L). They are the radiuses of the smallest centred in zero balls containing i linearly independent vectors, i.e. λ 1 (L) is the norm of a shortest non-zero vector of L, λ 2 (L) the norm of the second shortest vector and so on.

The Gaussian Heuristic (GH) states that the volume of the intersection of a set S and a lattice L is: Vol(S ∩ L) ≈ Vol(S)/Vol(L). Especially, it yields a useful estimate for the first minimum:

λ 1 (L) = � n 2πe Vol(L) 1/n
Finally, we introduce the Root Hermite Factor of a basis that we note δ 0 . For a given basis (b 1 , . . . , b n ), it is defined such that:

�b 1 � = δ n 0 • Vol(L) 1/n
It is clearly dependent of basis used to represent the lattice and, as we shall see next, plays a central role when speaking of basis quality.

Hermite's work from the 19th century provides us with the following inequality:

λ 1 (L) Vol(L) 1/n ≤ � 4 3 � n-1 4
Therefore we define the Hermite constant γ n as the extremum of the left side hand ratio over all lattices of a given dimension n. It is folklore that γ n grows linearly in n, yet exact value for it are only known for n from 1 to 8, and 24.

Lattice hard problems

The study of lattices by mathematicians goes far back in time with sphere packing analysis, but it is only recently that cryptologists got interested into them. First, with Coppersmith [START_REF] Coppersmith | Finding a small root of a bivariate integer equation; factoring with high bits known[END_REF] who used lattices to break RSA under some assumptions. Then Ajtai [START_REF] Ajtai | Generating hard instances of lattice problems[END_REF] opened the way to lattice-based cryptography, showing the existence of NP-hard problems in lattices. We review now the landscape of these hard problems, that support today all primitives of lattice-based cryptography, homomorphic encryption among them.

Shortest Vector Problem (SVP) and consorts

Shortest vector problems

The first (and easiest to state) of these problems is called the Shortest Vector Problem (SVP). This problem asks to find a shortest non-zero vector v in a lattice L, given a basis B. It shall satisfy �v� = λ 1 (L) Note that due to the group structure of lattices, the shortest vector is not unique, never. In every lattice, if v realises the first minimum, then -v does it too. There are also lattices were several linearly independent vectors have all the shortest norm (e.g. the hexagonal lattice).

The result of Ajtai [START_REF] Ajtai | The shortest vector problem in L 2 is NP-hard for randomized reductions[END_REF] is that the exact version of SVP is NP-hard.

Approx-SVP. If we relax the condition to finding a vector v, such that �v� ≤ γλ 1 (L) for some γ > 1, we have the Approximate Shortest Vector Problem (Approx-SVP). The greater the constant γ, the easier the problem. Assuming the Gaussian Heuristic, we can reformulate

�v� ≤ γ • λ 1 (L) ≤ γ • � n 2πe Vol(L) 1/n
Hence, a lattice reduction that achieves a root-Hermite factor of δ n 0 = γ � n 2πe solves Approx-SVP with approximation factor γ. Since LLL achieves δ n 0 = (4/3) (n-1)/4 in polynomial time, we can say that Approx-SVP with exponential approximation factor is not hard. There are several results about Approx-SVP hardness for intermediate approximation factor [START_REF] Micciancio | The shortest vector in a lattice is hard to approximate to within some constant[END_REF][START_REF] Aharonov | Lattice problems in NP ∩ coNP[END_REF].

Hermite SVP. For Approx-SVP, the factor bounds the short vector size with respect to the first Minkowski minimum, that we do not always know in advance. Therefore, if we refer to the volume instead: �v� ≤ γVol(L), we define the Hermite Shortest Vector Problem with approximation factor γ.

Unique SVP. As we shall see later, lattice-based primitives are such that the lattice contains one unexpectedly short vector. This might turn out to be a much easier problem that we refer to as the Unique Shortest Vector Problem (uSVP), which is about finding a shortest vector when λ 2 (L) > γλ 1 (L).

Gap SVP. Another variant of Approx-SVP is called GapSVP. This is a decisional version. It asks to determine, for a fixed factor γ, if a given lattice L verifies λ 1 (L) ≤ c or λ 1 (L) ≥ γ •c, with the promise that the lattices fall into one or the other case.

Closest vector problems

Where SVP is the homogeneous problem to find a lattice vector close to 0 ∈ L, we can also ask to find a lattice vector close to some target t ∈ R n . More formally, given a basis B of a lattice L of dimension n and a target t ∈ R n , find the vector v ∈ L such that �t -v� is minimal.

Approx-CVP.

As for SVP, we can define an Approximate Closest Vector Problem for an approximation factor γ. This version is about finding a vector v ∈ L such that

�t -v� ≤ γ • dist(L, t)
where dist(L, t) is the distance from t to the closest vector from t in lattice L. Both exact and approximate CVP are hard within constant factor [START_REF] Arora | The hardness of approximate optima in lattices, codes, and systems of linear equations[END_REF], furthermore any hardness result on CVP implies the same hardness for SVP [START_REF] Goldreich | Approximating shortest lattice vectors is not harder than approximating closest lattice vectors[END_REF], i.e. SVP is not harder than CVP.

Bounded Distance Decoding. If in addition, we have the promise that the closest vector is unique and that dist(L, t) < γλ 1 (L), we speak about the Bounded Distance Decoding (BDD) problem. This problem is one of the closest to the instances we see later, and we have a hardness result for it [START_REF] Lyubashevsky | On bounded distance decoding, unique shortest vectors, and the minimum distance problem[END_REF].

Learning with errors (LWE)

Using the previous problems, it is possible to construct some primitives for lattice-based cryptography, yet cryptographers looked for more expressive problems that would enable more advanced primitives. In 2005, Regev introduced the Learning with errors (LWE) problem [START_REF] Regev | On lattices, learning with errors, random linear codes, and cryptography[END_REF], which is about solving noisy linear equations. More formally, given two positive integers n (dimension), q (modulus) and a probability distribution χ over Z, we define the LWE n,q,χ problems as follows:

For a fixed secret vector s ∈ Z n q , we construct m samples (a, b) = (a, �a, s� + e), where a is sampled uniformly in Z n q and e is sampled from χ and considered in Z q . The Search problem is about recovering s from the available samples and the Decision problem is about distinguishing such samples from uniform samples in Z n q × Z q . Several hardness results have been demonstrated: classical or quantum, for different sizes of modulus q, in an normal form (secret and error are sampled from the same distribution). The condition that always remains is that the error distribution shall not be to small, otherwise the problem is not hard. To the extreme, if we have e = 0, it is only a matter of linear algebra to recover s.

A former problem: Learning Parity with Noise (LPN) [START_REF] Blum | Noise-tolerant learning, the parity problem, and the statistical query model[END_REF] is a particular case of LWE problem where q = 2 and χ is the Bernouilli distribution over {0, 1}.

Another convenient way to express the LWE problem with m samples is to adopt a matrix notation. With A ∈ Z m×n q where each row is an a from the previous definition and b and e are column vectors of the b's and e's, we can write

(A, b) = (A, As + e) ∈ Z m×(n+1) q .
In LWE-based schemes, A relates to the lattice basis.

Learning with errors over rings (Ring-LWE)

The use of LWE to construct schemes often implies many samples and therefore the matrix A tends to be expensive to store or share. Therefore, the community tried to find ways to gain efficiency in this matter. A solution is to add structure to the lattice and consider, for instance, ideal lattices. In this setting, the description of the lattice requires only a vector a instead of a matrix A decreasing the costs of the scheme from O(n 2 ) down to O(n). More precisely, we define the LWE problem over Rings (Ring-LWE) [START_REF] Lyubashevsky | On ideal lattices and learning with errors over rings[END_REF] as follows.

Given a ring R of degree n over Z and a positive integer q, we call R q = R/qR the quotient ring. We also fix χ a probability distribution over R. Then, for a fixed s ∈ R q , we construct m samples (a, b) = (a, a • s + e mod q) where a is sampled uniformly in R q and e is sampled from χ. The search problem asks to recover s from the samples and the decision version is to distinguish such samples from uniform samples in R 2 q . In terms of security, Ring-LWE enjoys security reductions to SVP in ideal lattices. So this cannot be harder than regular LWE. Yet as of today there is no significantly better algorithm to solve SVP in the ideal case. The algebraic structure is nevertheless an aspect that requires much attention. The original problem statement involves a fractional ideal R ∨ dual to R and therefore the statement above is equivalent from an application perspective but differs to some extent when doing their rigorous analysis.

Miscellaneous

Module-LWE

Working in highly structured lattices, e.g. ideal lattices, or even more so with cyclotomic rings, brings many concerns about real hardness of these instances. Therefore we see several attempts to trade-off between the higher efficiency of the structure and their weaker hardness results. One is to shift to non-cyclotomic rings and the other to module lattices and define module-LWE [START_REF] Langlois | Worst-case to average-case reductions for module lattices[END_REF] for instance. This problem generalizes Ring-LWE where the elements are not living in R q of dimension n but in R d q of dimension nd. This provides easy trade-offs and we see several primitive based upon it.

Middle-Product LWE

Another way to shift the LWE formalism is to change the binary operator between a and s. Instead of using the regular product, as in Ring-LWE for example, the idea is to use the middle-product operator. The middle product of size d of a and b, two polynomials of degree d a and d b is:

MP(a, b) = � ab mod x k+d x k � , where 2k = d a + d b -d -1
Interesting hardness results has been demonstrated for this problem [START_REF] Rosca | Middleproduct learning with errors[END_REF] together with efficient primitives.

Short Integer Solution

Another expressive problem, somehow dual to LWE, is the Short Integer Solution (SIS) problem. It was introduced even before LWE by Ajtai's work [START_REF] Ajtai | Generating hard instances of lattice problems[END_REF], but since it is more useful to construct signatures than encryption schemes, we prefer to mention it only as extra information, not at the core of this thesis work. Informally, SIS asks to find a linear combination, with small coefficients, of given random elements that yields zero. More formally, as with LWE we have a dimension n, a modulus q and m samples (a i ) 1≤i≤m ∈ (Z n q ) m , SIS asks to find (s i ) 1≤i≤m , each of norm �s i � smaller than some threshold t, such that � a i • s i = 0 ∈ Z n q . SIS enjoy hardness reduction to GapSVP as LWE. It also has an inhomogeneous version where the combination target is no longer 0 but some vector in Z n q , and also ring and module variants.

Presentation of FHE

We shall now introduce the core of this thesis: homomorphic encryption (HE). First with an overview on the history of the different scheme proposals that led to the current stateof-the-art in the subject. And then, we shall present the different common components of homomorphic encryption schemes, using that from Fan and Vercauteren [START_REF] Fan | Somewhat practical fully homomorphic encryption[END_REF] to illustrate.

Homomorphic Encryption history (2008-2017)

Homomorphic encryption dates back to the notion of privacy homomorphism whose existence was conjectured in the late 70s [START_REF] Ronald L Rivest | On data banks and privacy homomorphisms[END_REF]. The aim is to allow computation to take place over private data, e.g. encrypted data. The situation back then was that encryption scheme only allowed encryption and decryption. Any operation on ciphertext would give a completely uncontrolled decrypted plaintext, or worse, prevent its decryption.

The first step, to perform any operations, was to allow one type of operation. This is what we call partially homomorphic encryption whose most famous examples are the cryptosystem RSA [START_REF] Ronald L Rivest | A method for obtaining digital signatures and public-key cryptosystems[END_REF] and that of Paillier [START_REF] Paillier | Public-key cryptosystems based on composite degree residuosity classes[END_REF]. Indeed, two RSA ciphertexts can be multiplied together and yields an encryption of the product of their respective plaintexts. We say that RSA is homomorphic for multiplication. Similarly Paillier is homomorphic for addition. Other schemes provide homomorphism for multiplication or addition, but it is only in 2008 with the work from Aguilar-Melchor et al. [START_REF] Aguilar-Melchor | Additively Homomorphic Encryption with d-Operand Multiplications[END_REF] that it became possible to do both additions and multiplications on ciphertexts, at least a bounded number of them. It creates the concept of Somewhat Homomorphic Encryption (SHE) whose schemes permits a number of operations known in advance. Next, in 2009, Gentry [START_REF] Gentry | Fully homomorphic encryption using ideal lattices[END_REF] set the first stone to Fully Homomorphic Encryption (FHE), where no more constraints pertains to the computation. Thanks to the novel technique of bootstrapping which consists in homomorphically decrypting the ciphertext to refresh it, it becomes possible to evaluate any circuits on encrypted data. At least in theory because this early proposal is not efficient at all, but opened the road to many improvements. The first implementation of the ideas of Gentry is due to Smart and Vercauteren [?].

The first improvement was introduced with work from van Dijk et al. [START_REF] Van Dijk | Fully homomorphic encryption over the integers[END_REF], dubbed FHE over the integers. Instead of lattices like Gentry, they only use integers to construct their scheme, whose security relies on the hardness of Approximate Greatest Common Divisor (AGCD) problem. This problem asks, given several elements which are almost multiples of an integer p, to recover p. Several improvements have been brought to the original DGHV scheme until 2012 [START_REF] Coron | Fully homomorphic encryption over the integers with shorter public keys[END_REF][START_REF] Coron | Public key compression and modulus switching for fully homomorphic encryption over the integers[END_REF].

Then, many homomorphic encryption scheme were designed over LWE and ported to the ring setting for efficiency. Brakerski and Vaikuntanathan's scheme introduced several novel technique such as the modulus switching [START_REF] Brakerski | Fully homomorphic encryption from ring-LWE and security for key dependent messages[END_REF][START_REF] Brakerski | Efficient fully homomorphic encryption from (standard) LWE[END_REF]. This operation allows to scale down the noise inherent to the ciphertext which increases at each operation. This postpones the need for a bootstrapping. Also their scheme shows a linear increase of the error magnitude with respect to the circuit depth, unlike Gentry's scheme which has quadratic increase. Next, the modulus switching was pushed even further in BGV scheme [START_REF] Brakerski | leveled) fully homomorphic encryption without bootstrapping[END_REF], where a complete ladder of moduli is used, so that after each multiplication, the ciphertext is scaled down to the next modulus. This is what we call a leveled HE scheme. BGV is, as of today, one of the most promising scheme and an implementation is available in the IBM Research library HElib [Hal] with many implementation tricks [GHS12a, GHS12b, SV14]. Next, leaving modulus switching aside, Brakerski presented a scale invariant scheme over LWE [START_REF] Brakerski | Fully homomorphic encryption without modulus switching from classical GapSVP[END_REF], later transposed to Ring-LWE by Fan and Vercauteren [START_REF] Fan | Somewhat practical fully homomorphic encryption[END_REF]. FV is also very promising and is implemented by Microsoft Research in SEAL library [LCP17] and using NFLlib [Cry]. It also enjoys a fast variant using Residue Number System (RNS) [START_REF] Bajard | A full RNS variant of FV like somewhat homomorphic encryption schemes[END_REF]. Both BGV and FV belongs to the second generation of homomorphic schemes, Gentry's was the first generation.

We have also seen homomorphic schemes inspired by NTRU encryption scheme [START_REF] Hoffstein | NTRU: A ring-based public key cryptosystem[END_REF]. YASHE [START_REF] Joppe W Bos | Improved Security for a Ring-Based Fully Homomorphic Encryption Scheme[END_REF], which has similarities with FV, sounded very interesting, even at the beginning of this thesis. It was the original scheme in SEAL library. However, in 2016, the subfield/sublattice attack [ABD16, KF17] damaged completely the overstretched NTRU assumption that sustained YASHE.

Later, third generation schemes were introduced. They remove the need for relinearisation of the second generation proposals. GSW [START_REF] Gentry | Homomorphic encryption from learning with errors: Conceptually-simpler, asymptotically-faster, attributebased[END_REF] extends upon Brakerski's scheme [START_REF] Brakerski | Fully homomorphic encryption without modulus switching from classical GapSVP[END_REF], and SHIELD [START_REF] Khedr | SHIELD: scalable homomorphic implementation of encrypted data-classifiers[END_REF] is its ring variant. Similarly F-NTRU [START_REF] Doröz | Flattening NTRU for evaluation key free homomorphic encryption[END_REF] extended YASHE but became obsolete with the subfield/sublattice attack. Hence, SHIELD is the only interesting third generation scheme. It involves matrices where second generation schemes needed only vectors, therefore the minimal cost is higher, but thanks to the absence of relinearisation, the cost increases far slower than for previous generation schemes.

All the proposals from above are SHE, meaning that given a choice for their parameters, they can evaluate circuits of bounded complexity. The bootstrapping technique of Gentry can then be applied if the scheme parameters allow at least to evaluate the decryption procedure. For example, say that the procedure requires 8 multiplications, the scheme parameters shall be so that at least 9 multiplications are possible. In such cases, we can transform the SHE scheme into a FHE scheme. Sometimes it is not necessary if the application has a fixed number of multiplications for example.

Yet, the latest line of work is about bootstrapped schemes [AP14, DM15, BR15, CGGI16]. They have the property to maintain the noise level in ciphertext across the evaluation, removing the need for operations dedicated to bootstrapping. It is somehow built into the scheme. This proposals appeared quite recently and we have not yet applications using them, but they should ultimately be the best homomorphic encryption schemes.

Dimensioning constraints

As with any encryption scheme, the context of application is central to correctly setup the scheme and choose its parameter(s). From the end-user perspective, the scheme should adapt to two elements: the programme to evaluate P and the security level λ. Security is commonly evaluated in bits, λ bits of security means an attacker will face a cost of 2 λ to break the scheme.

Concerning the programme, we (designers) classically view it as a circuit with elementary gates, which then can be viewed as a polynomial function on the input data. For SHE/SHE schemes (e.g. BGV, FV) the main feature to consider is the circuit depth L. We usually define it as the maximum number of multiplications that an input data goes through to produce the output. Indeed, the multiplications are the operations that have the most impact on the noise in ciphertexts. And since we want to keep this noise under control to maintain decryption correct, this number of multiplications is the most important feature. For bootstrapped schemes, which usually offer more expressive gates that just addition/multiplication, the concerns are a bit different. We shall come back to that later in this work.

For cases like FV, we now have a depth L and security parameter λ and shall derive scheme parameters so that the computation will be both correct and secure. We shall see later that these two goals bring opposite conditions that may turn out contradictory. In the end, since our schemes are based on (Ring-)LWE, the parameter choice will give us at least a dimension n, a modulus q and an error distribution χ.

One example: the Fan-Vercauteren scheme (FV)

To illustrate the different components of a homomorphic encryption scheme, we take the one of Fan and Vercauteren [START_REF] Fan | Somewhat practical fully homomorphic encryption[END_REF], which is central for this thesis work.

FV is the ring variant of the scheme from Brakerski [START_REF] Brakerski | Fully homomorphic encryption without modulus switching from classical GapSVP[END_REF] and therefore all operations of FV are done in some ring R. The original description of FV sets R to be the polynomial ring R = Z[x]/(f (x)) for some monic irreducible polynomial f ∈ Z[x] of degree n. For easy exposition, we often choose f to be cyclotomic: f (x) = x n + 1 with n a power of 2. The elements at hands are polynomials of degree n, and we restrict to R q where the polynomials have their coefficients in Z q , for some positive integer q.

Key generation

The secret key generation is a fairly simple operation, but for efficiency purposes, it may differ between implementations. The original procedure is to sample the coefficients from a discrete Gaussian distribution χ s of standard deviation σ s .

s k = s = (s 1 , • • • , s n ) ∈ R q , where ∀i, s i ← χ s
Sometimes we see that s is binary (coefficients in {0, 1}) or ternary (coefficients in {-1, 0, 1}) or even sparse (only a fixed number of coefficients are non-zero).

The public key is then derived from s k . Sample a uniformly random a ∈ R q and an error e from a discrete Gaussian distribution χ e of standard deviation σ e . Then define

p k = (p 0 , p 1 ) = (-(a • s + e) mod q, a) ∈ R 2 q
We notice that this public key is a Ring-LWE sample. The error distribution may or may not be the same as the secret. However, error sampling is not trivial and should be done with care, especially while taking into account the ring R. As a reminder, the hardness results on Ring-LWE considers not R but R ∨ and this difference should be understood when implementing the error sampling.

Encryption and decryption

In FV, the plaintext space is R t , the set of polynomials of degree n with coefficients in Z t for some positive integer t, and the ciphertext space is R q . We note Δ = �q/t�.

To encrypt a message m ∈ R t , sample a binary polynomial u ∈ R 2 and two errors e 1 and e 2 from χ e , then set

c = (c 0 , c 1 ) = (Δ • m + p 0 • u + e 1 , p 1 • u + e 2 ) ∈ R 2 q
It is worth to note that homomorphic encryption schemes are often public encryption scheme and always random, two encryptions of the same plaintext must be independent from one another.

For decryption, compute

c 0 + c 1 • s = Δ • m + p 0 • u + e 1 + (p 1 • u + e 2 ) • s = Δ • m + (-(a • s + e) + a • s) • u + e 1 + s • e 2
which yields Δ • m, plus small polynomials. Hence by scaling and rounding we can recover

m = �(c 0 + c 1 • s) × t/q� ∈ R t
We can see that for decryption to work, the errors shall remain small. We will come back more extensively on this aspect later in this work.

Homomorphic addition

Performing addition with FV is not a complex operation, as is often the case with other SHE. Addition is a linear operation, so if we have c a and c b two encryptions of m a and m b respectively, then it is easy to verify that

c + = (c 0 + , c 1 + ) = (c 0 a + c 0 b , c 1 a + c 1 b ) ∈ R 2 q is a ciphertext for m a + m b .
The input noises are added to form the output noise.

Homomorphic multiplication

Multiplication is a more involved process. Indeed, we would like that the decryption of c × yields the same as the product m a and m b . In other words we wish that

�(c 0 × + c 1 × • s) × t/q� = �(c 0 a + c 1 a • s) × t/q × (c 0 b + c 1 b • s) × t/q� = �c 0 a • c 0 b + (c 0 a • c 1 b + c 1 a • c 0 b ) • s + (c 1 a • c 1 b ) • s 2 × t 2 /q 2 �
However we have in the right-hand side a term in s 2 that makes this straightforward product a non-valid ciphertext. This is why we need to perform a relinearisation of the quadratic term in order to get c 0 × and c 1 × so that the equality holds. For other schemes this operation may be referred to as a key switching because the trick is about taking the part that is somehow encrypted under s 2 and getting it back encrypted under s.

Relinearisation.

To do this we need to make another, non negligible, assumption for security: we need circular security, that is to say we need to encrypt elements highly related to s under that same key s. This extra assumption is universal in homomorphic encryption scheme and it would be a huge leap forward to describe a new scheme that does not need it.

In practical terms, we can construct an almost encryption of s 2 by c r = (-(a

• s + e) + s 2 , a) ∈ R 2
q for some a and e as before. It holds that c

0 r + c 1 r • s = s 2 + e.
Provided this c r is public, we can then replace the s 2 terms by linear terms at the cost of an extra error. Yet, this is not good enough because this extra error will be multiplied by the term in front of s 2 in the equation above, i.e. a (non-small) uniform element of R q , so the error will blow up. The way to handle this is to slice this term (consider its decomposition in some basis ω), this process is referred to as the gadget decomposition. Then, with the appropriate relinearisation keys, it is still possible to get rid of the s 2 while maintaining the error growth under control. As we shall see later, the choice of ω is a trade-off choice between a bigger relinearisation key to share and a smaller error growth.

Chapter 3

Recipe for a new attack

. . 52

In this chapter we adopt an attacker posture in order to assess the security of homomorphic encryption schemes. In the previous chapter, we said that homomorphic encryption schemes sit on hardness results and are proven secure, even against quantum attackers. Such statements speak about asymptotic behaviour; they mean that it is possible to choose the parameters of a problem such that solving it is infeasible within some resource limit. In concrete terms it says that if we pick a parameter (e.g. a dimension) big or small enough, the attacker will not be able to solve the problem with his available resources.

Therefore, when given an concrete application, we have to put a cursor on the security level we want to achieve. We usually speak in terms of bit security, noted λ. Then, we say that our scheme has a security of λ bits of security, if we estimate the cost of the attack (e.g. time, space, money. . . ) to be in the order of magnitude of 2 λ . As a result, we need to have some link between the parameters of the scheme and the security level. This link is necessarily obtained by a similar link between the parameters of the underlying lattice problems (SVP, LWE, . . . ) and their concrete hardness. In this work, we are especially interested in that of LWE and its ring variants.

The present chapter begins with a review of the known attacks against (Ring-)LWE. Then we present our first contribution: a dedicated attack on LWE instances as found in homomorphic encryption settings. This work was accepted to IndoCrypt 2017 conference [START_REF] Bonnoron | A note on ring-lwe security in the case of fully homomorphic encryption[END_REF]. Finally, we report some contributions made on lattice reduction, which is a central part in most of the attacks. These contributions were mostly done on the fplll library [dt17] during coding days.

Review of the existing attacks

Just before this thesis began, Albrecht et al. released the survey Concrete hardness of Learning with Errors [APS15] which served as an excellent springboard in the subject for us. In addition to their work, they provided and maintain an lwe-estimator [Albb] which computes the expected attack costs against LWE with the input parameters. As we discussed in the previous chapter, Ring-LWE instances can be viewed as special cases of LWE instances, so all the attacks against LWE can be used against Ring-LWE.

Against LWE

Let us now review the different attacks against LWE.

Algebraic attack -Arora-Ge

The first attack we present here is that of Arora and Ge [START_REF] Arora | New algorithms for learning in presence of errors[END_REF]. It is an algebraic attack that establishes a system of non-linear noise-free polynomials, whose roots are the secret s. This attack assumes that the errors remain in some small range [-e; +e] because this value e determines the degree of the polynomials and also the number of samples we need for a valid resolution. Consequently, this is an interesting attack, because it is subexponential when the LWE error distribution is smaller than what the hardness reduction requires. It strengthens the fact that errors should not be too small. At least in theory, because this attack comes with large constant costs and despite its subexponential time, it is never an efficient way to attack LWE.

Combinatorial attacks -BKW

The Blum-Kalai-Wasserman method [START_REF] Blum | Noise-tolerant learning, the parity problem, and the statistical query model[END_REF] was introduced against the Learning Parity with Noise problem, a special case of LWE we mentioned earlier. From a global perspective, BKW-like algorithm are about using many LWE samples to create collisions and exhibit relations between samples that allow to reveal the secret. Since its introduction, many improvements have been brought to this line of work [AFFP14, ACF + 15b, DTV15, GJS15, KF15]. The main drawback is that these algorithms require many samples to work.

Lattice attacks -Primal and dual

Last, but not least, the lattice attacks. This family regroups the methods working with the structure of lattice behind the LWE samples and attempting to solve the equivalent BDD, CVP or SVP instances. The most natural is that of decoding. Assuming we are given an LWE sample (e.g. a public key from Fan-Vercauteren scheme) A • s + e and the description of the lattice A, we try to remove the error e to recover the lattice point A • s which then allows to recover s. This is solving a BDD instance. Below we present more extensively the algorithms [Bab86, LP11, GNR10, LN13] for this and our contribution.

As we shall see, in order to decode it is sometimes better to embed the lattice. That is, to consider the elements of A in another, bigger, lattice. This is what Kannan [START_REF] Kannan | Minkowski's convex body theorem and integer programming[END_REF], or Bai and Galbraith [START_REF] Bai | Lattice decoding attacks on binary LWE[END_REF] do. We will present these techniques in more details below. It allows to reduce BDD to uSVP [AFG14, AGVW17].

Finally, instead of working in the primal or direct lattice, it is also interesting to work with the dual lattice, as in [Alb17].

Against Ring-LWE

As we said above, Ring-LWE can be considered as a special case of LWE, but the additional ring structure may make dedicated attacks possible. We recently saw this trend in the following works [EHL14, ELOS15, CLS15, CLS16, CIV16] which were summed up by Peikert [START_REF] Peikert | How (not) to instantiate ring-LWE[END_REF]. All these works take advantage of the error distribution shape in the ring. Hence, none of them invalidates the hardness result about Ring-LWE [START_REF] Lyubashevsky | On ideal lattices and learning with errors over rings[END_REF] which specifies that the errors should be sampled in R ∨ and not in R. Nevertheless, the difference allows to mount attacks against careless error sampling. Peikert shows how to instantiate Ring-LWE securely.

When presenting the ring-based homomorphic encryption schemes, we mentioned YASHE [START_REF] Joppe W Bos | Improved Security for a Ring-Based Fully Homomorphic Encryption Scheme[END_REF] and F-NTRU [START_REF] Doröz | Flattening NTRU for evaluation key free homomorphic encryption[END_REF] that are based on the hardness of the NTRU assumption (not only on that of Ring-LWE). However, for performance considerations, the choices of parameters that the authors advertised were not compliant with the hardness result about NTRU [START_REF] Stehlé | Making NTRU as secure as worst-case problems over ideal lattices[END_REF]. Therefore we saw successful attacks against them [ABD16, KF17].

Mounting our own dedicated attack

We just described the landscape of attack methods against (Ring-)LWE instances. Remember that when dealing with LWE, we have a dimension n for the samples, a modulus q and an error distribution, say Gaussian with standard deviation σ. We shall see more precisely in the next chapter what values these parameters take in the case of Fan-Vercauteren scheme. Typical values are: few thousands for n, some hundreds of bits for q and σ gets as tiny as 8, despite the hardness reduction that requires σ > 2 √ n.

So such parameter set is quite remarkable, q is huge and σ is tiny. Based on this analysis and on the fact that, at the beginning of this thesis, no attacks make any particular assumptions on the parameter values, we started to investigate what could be done in this case and what performance an ad-hoc attack could achieve. This work was mostly done in the first year of my thesis and was accepted to IndoCrypt 2017 as A Note of Ring-LWE security in the case of Fully Homomorphic Encryption. Some of the material below is extracted from that work.

Outline

Among the available attacks, some are dedicated to the case where the secret is small, for example BKW [START_REF] Albrecht | Lazy modulus switching for the BKW algorithm on LWE[END_REF] or embedding [START_REF] Bai | Lattice decoding attacks on binary LWE[END_REF] variants. We started by following the path of lattice attacks using decoding approach. This choice stems from the fact that with Fan-Vercauteren application, the public key is one (Ring-)LWE sample and may be attacked offline. Combinatorial attacks would require a huge amount of samples so they seemed less practical. As a running thread for this whole thesis, we shall use Fan-Vercauteren scheme to illustrate our attack.

For the public key to the lattice From (Ring-)LWE samples it is possible to create a straightforward lattice. We show here how this is done and stress on the main difference between LWE and Ring-LWE cases and why it matters.

In the LWE case, when we have access to m samples of The second term of the pair b is, in the q-ary lattice L(A), the point As mod q to which some noise e has been added.

Z n q × Z q : (a 1 , b 1 ) = (a 1 , �a 1 , s� + e 1 mod q) (a 2 , b 2 ) = (a 2 , �a 2 , s� + e 2 mod q) . . .
In the Ring-LWE case, the situation is slightly different. A matrix A ∈ Z n×n q can be derived from a single sample. With a = (a 1 , a 2 , • • • , a n ) ← R q and s ← R 2 , we have the identity a • s = As. For easy exposition, if we set n to be a power of two and R = Z[X]/(X n + 1), the matrix A is skew-circulant:

A =        a 1 a 2 a 3 • • • a n -a n a 1 a 2 • • • a n-1 -a n-1 -a n a 1 • • • a n-2 . . . . . . . . . . . . . . . -a 2 -a 3 -a 4 • • • a 1       
The matrix A differs for other cases of n and R, but the result is the same: with only one Ring-LWE sample, we can mount a lattice attack to attempt to recover s.

Embedding and rescaling

Now that we have a lattice basis A ∈ Z n×n q and a vector b ∈ Z n q , we want to find s and/or e both in Z n q . The attack from Bai and Galbraith goes as follows.

Where is the lattice problem? First, write

A � = (A|I n ) ∈ Z n×2n q .
We have the following equality

b = A � � s e � mod q
where � s e � is a short vector, with respect to q, that we want to reveal.

Given A and b, we can find a trivial solution w = � 0 b � that gives A � w = b. However w is not small, and clearly not the solution we expect. So now that we have a particular solution, we want to find a solution v 0 to the homogeneous problem, i.e. A � v 0 = 0 mod q.

For such a vector v 0 , we have

A � (w -v 0 ) mod q = A � w -A � v 0 mod q = b -0 mod q = b If in addition v 0 is such that w -v 0 is small, it is most likely that w -v 0 = � s e � .
Consequently, we consider the lattice L � defined by L � = {v ∈ Z 2n : A � v = 0 mod q} and try to find a vector v 0 close to w in it.

We recognise a CVP instance: L � is the lattice and w is the target. We now need a basis for L � and then we can follow with classical CVP algorithms. Besides, if we know how s and e have been sampled, we can derive a bound on �wv 0 � and this becomes a BDD instance.

Embedding. Luckily, it is fairly straightforward to explicit a basis for L � , by embedding:

B = � I n -A 0 qI n � ∈ Z 2n×2n
It can be verified that the rows of this matrix are linearly independent and each of them satisfies the definition of L � , so B is a basis of L � .

This embedding differs slightly from what Bai and Galbraith presented. They instead introduced the matrix

M = � I n -A qI 2n � ∈ Z 3n×2n
and compute its Hermite Normal Form to end up with a full rank matrix generating the lattice. Our technique avoids this computation and yields a basis for L � more efficiently.

We can see that with linear operations on rows their M can be transformed into our B as follows:

M =   I n -A qI n 0 0 qI n   →   I n -A 0 qA 0 qI n   →   I n -A 0 0 0 qI n  
Removing the n middle rows gives our matrix. As the name suggests, the Hermite Normal Form is useful for theoretical discussions and analyses but an attacker would definitely not go this way. This is why we changed the embedding step.

Rescaling. So far we did not take any advantage of the parameters values, yet in real applications secrets and errors are sampled very differently. Usually s will be ternary whereas e is sampled from a Gaussian for standard deviation σ, which in theory should not be small. Consequently the distance from w to L � is not balanced along each dimension because

w -v 0 = � s e � .
The idea is to take advantage of that to inflate the lattice. If we consider instead a basis

B = � σI n -A 0 qI n � ∈ Z 2n×2n
the difference between w and the closest vector in this lattice becomes � σs e � which is more balanced. It is useful to do this, because now the lattice volume is bigger so lattice reduction algorithms will give better results. It slightly increases the distance between the lattice and the target but it is worth it.

BDD algorithms

Once the embedding and rescaling is done, the next step is to find the closest point v 0 to w in L � . The available BDD algorithms need a well-reduced basis to work efficiently. This is not the case of our basis B. In the next sections we present our experiments and contributions to the field and see what strategy an attacker would follow.

Expanding on reduction

We already mentioned in the previous chapter that lattice reduction draws many contributions both on theoretical questions and implementation aspects. As we see in this work, the lattice reduction performance and complexity greatly define the security level of a choice of parameters. The previous embedding and rescaling are trivial and costless operations, however breaking BDD is a much more costly task. Since a better reduction allows for a faster enumeration, an attacker would try to balance the time spent in both steps. Hence it is paramount to understand lattice reduction behaviour to provide correct security guarantees.

Ad-hoc algorithms

Based on experimental studies [GN08b, MW16], it seems a natural choice to pick the BKZ algorithm. It achieves quite good reduction, with possible trade-offs on complexity and quality (via the blocksize parameter β). But these experiments are based on general random lattices. The lattice at hand here is very particular: integer, upper triangular, blockwise upper triangular, with scaled identity on the diagonal. The attacker may look for specialised lattice reduction algorithm.

To the best of our knowledge, only one specialised algorithm, a variant of LLL by Gama et al. [START_REF] Gama | Symplectic lattice reduction and NTRU[END_REF] may be useful in our case. It is a study about NTRU attack and the lattices that the authors aim at reducing are symplectic. A lattice with basis B is symplectic if and only if

B T J 2n B = J 2n , where J 2n = � 0 I n -I n 0 � ∈ Z 2n×2n
The bases of our case are symplectic, as can be verified. So this variant of LLL would be interesting to try. The authors claim it brings a speed-up factor of nearly 10 when compared to reference implementations of regular LLL. However the code has not been released, so we could not use it in our tests, nor confirm its performance. This is one example of specialisation that could bring unexpected computational advantage to an attacker. Despite our efforts we were not able yet to come up with another reduction method for this specific case of embedding. The size of the lattice being doubled by the embedding, the reduction time is drastically increased. Consequently working on the original lattice A before embedding might give a fantastic gain compared to what we present below. We leave this topic for further research.

Tweaking LLL

After a few toy examples we realized that most of the time was spent in the lattice reduction stage. So we tried different settings for BKZ and also for LLL on cases where n ≤ 100. It turned out that LLL reduction was good enough for our instances, and even a weak LLL reduction.

Concerning BKZ, we could confirm [START_REF] Chen | BKZ 2.0: Better lattice security estimates[END_REF], an intermediate blocksize β = 20 leads to moderate running times. Whereas smaller values like 5 or greater like 40 lead to higher running times.

Concerning LLL, we recall the size reduction and Lovász conditions:

∀i < j, |�b j , b � i �| ≤ η • �b � i � 2 ⇐⇒ µ i,j ≤ η ∀i, δ�b � i � 2 ≤ �b � i+1 � 2 + (b i+1 |b � i ) 2 �b i � � 2
We always have 1/4 ≤ δ ≤ 1 and 1/2 ≤ η ≤ √ δ and the default value is (δ, η) = (0.99, 0.51). We first tried to decrease δ to loosen the Lovász condition. However with an LLL-(0.75, 0.51), we see speed-ups only for n ≥ 100 and the overall attack fails later due to a lattice basis of not sufficient quality.

So we then worked on η, trying to increase its value while keeping δ = 0.99. We performed experiments with the following η: 0.60, 0.75, 0.80, 0.85, 0.95, 0.98. As we can see in Figure 3.1, loosening the size reduction condition decreases the running time of LLL. We observe a speed-up even in moderate dimensions. This speed-up is greater between η = 0.60 and η = 0.75 than between η = 0.75 and η = 0.95. In addition, with η = 0.95 we get a less successful attack, whereas when η equals 0.50 or 0.75 the success rates are similar. We conclude that the best option is around η = 0.60.

Consequently, in our specialised attack, the best choice for the lattice reduction step is an LLL reduction, with δ = 0.99 and η ∈ [0.60, 0.75].

The actual decoding step

To perform the final search for the closest vector of v 0 in the lattice L � , we have several options. There are sieving algorithms [START_REF] Shi Bai | Tuple lattice sieving[END_REF][START_REF] Herold | Improved algorithms for the approximate k-list problem in euclidean norm[END_REF] and enumeration algorithms [START_REF] Fincke | Improved methods for calculating vectors of short length in a lattice, including a complexity analysis[END_REF][START_REF] Gama | Lattice enumeration using extreme pruning[END_REF], with also Gaussian sampling [START_REF] Aggarwal | Solving the shortest vector problem in 2 n time using discrete Gaussian sampling: Extended abstract[END_REF][START_REF] Aggarwal | Solving the closest vector problem in 2 n time -the discrete Gaussian strikes again![END_REF] or Voronoi cell computation [MV10] techniques.

From an attacker's point of view, today the enumeration algorithms are best, especially what is called pruned enumeration [START_REF] Liu | Solving BDD by enumeration: An update[END_REF]. This method is an adaptation to BDD of the extreme pruning technique introduced by Gama et al. [START_REF] Gama | Lattice enumeration using extreme pruning[END_REF]. Conceptually, enumeration is about trying many linear combinations of basis vectors to find vectors that are small (in the case of SVP) or close to the target (in the cases of CVP or BDD). If we do not put any constraints, enumeration generates all the lattice vectors. This is a sure way to find the one we look for, but unimaginably costly. So in practice, we want to enforce some condition to keep the enumeration tree size under control.

The most elementary way to perform an enumeration comes from Babai [START_REF] Babai | On Lovász'lattice reduction and the nearest lattice point problem[END_REF] Nearest Plane algorithm. Assume we have our reduced basis B = (b 1 , • • • , b n ) and we want to approximate w / ∈ L � . We can express exactly w with a real linear combination of the Gram-Schmidt vectors:

w = n � i=1 t i b � i , where ∀i, t i ∈ R.
So if we iteratively round each t i , and update the target to account for the rounding at every dimension, we can get a vector v ∈ L � rather close to w in polynomial time. More precisely, v is the unique vector such that wv ∈ P 1/2 (B � ). However v is not always the closest vector to w, so Lindner and Peikert [START_REF] Lindner | Better key sizes (and attacks) for LWEbased encryption[END_REF] generalised this algorithm into the Nearest Planes algorithm. In this version, instead of keeping only the rounded coefficients, a bounded exhaustive search is performed to keep more than one candidate at each dimension.

The next level of generalisation is what we call pruned enumeration. This time, at each depth in the tree (i.e. when considering each component of w), we want to choose a candidate component for v i the i-th coordinate of the solution v we search. So we look at the quantity �wv, b � i �/�b i � �, and consider all values for v i such that this quantity remains below some bound R i . We call the tuple (R 1 , • • • , R n ) the pruning function. This is the only setting for the last attack step.

In our case, we know precisely the expected distance between w and the lattice point v 0 , w -v 0 = ( σs e ), so we can set the bound R n to the expected value of its norm. For a Gaussian error distribution we have with high probability ||e|| 2 ≤ n × (3σ 2 ), so R 2 n = nσ 2 + n(3σ) 2 = 10nσ 2 . It remains to explore how to set the other R i 's. Gama et al. [START_REF] Gama | Lattice enumeration using extreme pruning[END_REF] study different remarkable functions: linear, step bounded or piecewise linear. Their results is that extreme pruning is the most efficient regime. Extreme pruning is about having very low bounds R i so that the enumeration tree is very small and quickly scanned. In this case however, the probability of success for finding the correct solution is very low, so we need to shuffle the basis and start again lattice reduction and enumeration multiple times.

Despite this state-of-the-art, we noticed with our instances that the correct solution was almost always the Babai solution, that is the first candidate to be enumerated. We provide explanation for this fact below.

Launch the attack, for real

In order to practically evaluate the performance of the ad-hoc attack described above, we implemented it and ran many experiments against real instances, leading to successful breaks.

Early experiments

Our first rounds of experimentation were done using a custom implementation in C++. We made use of the following libraries:

• Lepoint's implementation [START_REF] Lepoint | A proof-of-concept implementation of the homomorphic evaluation of SIMON using FV and YASHE leveled homomorphic cryptosystems[END_REF] of Fan-Vercauteren. At that time (2015), SEAL [START_REF] Laine | Simple Encrypted Arithmetic Library -SEAL v2.3[END_REF] had not yet shifted to FV, but today we would rather use SEAL instead.

• fplll [dt17] for lattice reduction algorithms,

• NTL [Sho] for additional lattice operations.

We implemented the embedding/rescaling, the pruned enumeration algorithm from Liu-Nguyen following their pseudo-code [START_REF] Liu | Solving BDD by enumeration: An update[END_REF] and created the glue between the different libraries to lead the attack from beginning to end.

Lepoint's implementation. In order to compare FV and YASHE [START_REF] Lepoint | A comparison of the homomorphic encryption schemes FV and YASHE[END_REF], Lepoint implemented the code needed to use FV scheme and perform homomorphic operations. We use his constructor method with light modification. It allows us to create a public key pk = ([-(a • s + e)] q , a), given n, σ and q. The attack then works with an FVKey object as input.

We run these experiments against FV public keys of fairly wide ranges of parameters: 30 ≤ n ≤ 360 and 10 ≤ q ≤ 2 128 keeping σ = 2

√ n (i.e. best choice for FHE, within the LWE hardness bounds). For lattice reduction, we kept η ∈ {0.51, 0.61, 0.71}.

With n up to 250 we see in Figure 3.2 that with η = 0.71 the attack takes fairly less time than 0.51, roughly 5 times less and still finishes successfully. This motivated us to keep only the version η = 0.71 and continue to higher dimensions.

In the end we were able to successfully break an FV key with n = 320 and log q = 68 in little less than 29 hours, see Figure 3. 3. It seems in reach to beat the previous record from Laine and Lauter [START_REF] Laine | Key recovery for LWE in polynomial time[END_REF]. They were able to recover a key in dimension 350 in 3.5 days, with a less generic attack with log q = 52 and σ = 8/ √ 2π.

Here we say that we were successful in our attack, meaning we successfully recovered the private key from the public key with the settings we discussed above: LLL reduction with η = 0.71, δ = 0.99 and Babai enumeration, i.e. the attack is only made of polynomial time components. If it would scale, it would have been an issue for lattice-based homomorphic encryption schemes. However, beyond the successful instances we also had failures, for smaller q, and/or bigger n. Therefore we made thorough analyses of success/failure cases, to push this polynomial time attack as far as possible.

We distinguish several situations:

• Wrong when the attack goes as planned and output a vector, but not the correct secret, • Failure when Babai enumeration does not succeed in finding a candidate of expected norm.

Looking at lattice reduction indicators, as shown in Figure 3.4, was unfortunately not enough to divide Success from Failure cases.

Decoding from fplll

Later, during our study of Success and Failure cases, we dived into fplll source code and found that, in addition to the reductions and SVP routines, there was also a CVP routine, flagged experimental. We defer to the next section the details about the work on fplll that followed. Soon enough we were able to replace our own implementation of pruned enumeration with a respected library alternative. So, we launched again the attack on the same instances as before, for the sake of comparison. It turned out that the results were almost the same, in terms of Failure or Success. The only improvement with fplll version was on small dimension and huge modulus cases of Failure, which all became Success, probably thanks to a more clever floating-point precision management in fplll.

Looking at Babai's Nearest Plane algorithm provides an explanation of the ceiling our attack faces. No successful break happens above n = 340. Indeed, we said that Babai algorithm recover the unique vector v such that w -v ∈ P 1/2 (B � ), so our attack is successful if and only if

� s e � ∈ P 1/2 (B � ).
In other words, with a fixed lattice reduction, the b � i are also fixed and only an error e that validates |�e, b � i �| < �b � i � 2 /2 can be handled successfully. In the LWE case, it is possible to derive a success probability for the Nearest Plane algorithm, depending on the standard deviation of the error and the norm of the Gram-Schmidt vectors [START_REF] Lindner | Better key sizes (and attacks) for LWEbased encryption[END_REF]:

P = n � i=1 erf � �b � i � √ π 2σ �
where erf is the Gauss error function. We can exhibit this graphically. In Figure 3.5 we plot the Gram-Schmidt norms of the bases vectors, for reduced lattices of increasing sizes. We also plot the expected error sizes for these dimensions. We can see that, with an increasing dimension, the norm of the smallest Gram-Schmidt vector get smaller while the error norm gets bigger. So obviously, for a fixed reduction, there is a maximal dimension beyond which Babai algorithm cannot be successful.

Easier from Sage

Much later, with the knowledge that this polynomial time attack was limited, we reconsidered the lattice reduction step, in order to push further the successful breaks. Our motivation stems from the fact that third generation homomorphic encryption schemes work with much small dimensions than the second generation (one thousand instead of many thousands). For the new round of experiments, we moved to SageMath environment. It gives access to the efficient fplll core routines, thanks to the Python wrapper fpylll [Alba] and allows for Our ultimate goal was to come close to the parameters of SHIELD [START_REF] Khedr | SHIELD: scalable homomorphic implementation of encrypted data-classifiers[END_REF]. For 80 bits of security they give: n = 1024, log q = 31 and σ = 10. In the end we could not go very far. We report in Table 3.1.

Conclusion

In this chapter we presented our work on the construction of a dedicated attack to the LWE instances of homomorphic encryption. This has been published at IndoCrypt 2017 [START_REF] Bonnoron | A note on ring-lwe security in the case of fully homomorphic encryption[END_REF].

At the time of this study, there were no similar work and people were expecting our outcomes. Despite its minor extent, our work has set a first stone to special-purpose attacks against homomorphic encrytion. The state-of-the-art today is the work from Albrecht [START_REF] Albrecht | On dual lattice attacks against small-secret LWE and parameter choices in HElib and SEAL[END_REF]. We think we can expect many other specific works like ours and we need them to gain confidence in homomorphic encryption.

This first work on attack made us dive into the state-of-the-art on cryptanalysis of lattice based cryptography. Among others we discovered lattice reduction challenges which are addressed in the next chapter.

Throughout this cryptanalytic work we grasped the wide range of theoretical and practical results. The spread of outcomes is such that one can easily get lost. This contribution has really been a hands-on work and it served as a good start to address our next topics with more confidence.

Chapter 4

Contributions to lattice reduction

Size

Lenstra-Lenstra-Lovász (LLL

Performances and output

Improving reduction

The

Proven

2-phases

Review of reduction algorithms

A central family of algorithms in our discussions is that of lattice reduction algorithms. In order to manipulate a lattice, we usually handle a family of vectors that spans the lattice, the basis. Therefore the legitimate question is whether there are more efficient representations (i.e. better bases) than others, and to what criteria. Then the challenge will be to somehow improve the basis.

As shown in Figure 4.1, the second basis seems much better than the first. The experimental intuition we have is that the vector lengths are more balanced and the vectors are closer to orthogonal from one another. While this is trivial to grasp and achieve in dimension 2, it is far from being the case in higher dimensions.

The operation of taking a basis from a lattice and making changes to it in order to improve its quality is called lattice reduction. We present here the different algorithms from

b 1 b 2 b � 1 b � 2 Figure 4.1 -Reducing the bad (red) basis (b 1 , b 2 ) to a better (blue) basis (b � 1 , b � 2 )
the literature and the performances. Many of the criteria involve the Gram-Schmidt vectors as defined above.

Size reduction

The most elementary reduction is about balancing the sizes of the vectors. We say a basis

B = (b 1 , . . . , b n ) is size reduced with parameter η ≥ 1/2 if ∀i < j, |�b j , b � i �| ≤ η • �b � i � 2 ⇐⇒ µ i,j ≤ η
The algorithm to achieve size-reduction is very simple and runs in polynomial time. It consists, for each vector, in subtracting the component of the current vector with respect to the previous vectors.

Unless specified, the parameter is set to η = 1/2 in the literature. Though we can see that the smaller the η, the tighter the inequation and the better the reduction becomes.

Lenstra-Lenstra-Lovász (LLL) reduction

The celebrated work from Lenstra, Lenstra and Lovász [START_REF] Klaas Lenstra | Factoring polynomials with rational coefficients[END_REF] presents a better lattice reduction algorithm dubbed LLL. It produces a basis that is size reduced, and validates the so-called Lovász condition:

∀i, δ�b � i � 2 ≤ �b � i+1 � 2 + �b i+1 , b � i � 2 �b i � � 2
LLL algorithm also runs in polynomial time in the input basis. Both the dimension and the entry size matter for the complexity and for the implementation. Indeed, implementing a floating-point version of LLL is a real challenge and many efforts have been done in this area.

The parameter δ can be tweaked to achieve different output quality. The default value for LLL implementation is δ = 0.99. We shall always keep δ ∈]1/4, 1] and η ∈ [1/2, √ δ[.

Blockwise algorithms

As generalisation of LLL, whose Lovász condition considers only a vector and the next at the same time, a new family of algorithms working on blocks was developed.

In BKZ (Blockwise Korkine-Zolotarev) algorithm [START_REF] Schnorr | Lattice basis reduction: Improved practical algorithms and solving subset sum problems[END_REF], the basis is first LLL-reduced for some η and δ. Then the algorithm works on a block of size β. The block is the space spanned by the projections of b j , . . . , b j+β orthogonally to (b 1 , . . . , b j-1 ). In this block, the algorithm searches for a short vector, then inserts it in the local basis and call LLL on the new expended vector family to keep β vectors. Thus a BKZ-reduced basis is LLL-reduced and we have the extra property that:

∀1 ≤ j ≤ n, �b � j � = λ 1 (L [j,k] )
where k = min(n, j + β -1) and L [j,k] is the lattice spanned by (π j (b j ), . . . , π j (b k )). In the case where β = n, we speak about Hermite Korkine-Zolotarev (HKZ) reduced basis.

While HKZ reduction is a useful notion in theory, in practice it is never attempted because of the time it would need. BKZ, as described here, is no longer used either. Several heuristics have been introduced to improve its performance and reduce its execution time. All these improvements are dubbed BKZ 2.0 [CN11] and we shall present our further improvements later. BKZ 2.0 is the state-of-the-art in terms of time and quality.

Self-dual BKZ. A new approach has been presented by Micciancio and Walter [MW16]: Self-Dual BKZ (SDBKZ). In BKZ, each tour look one block after the other towards increasing indices and extract a short vector in each block. In addition to these forward tours, they perform backward tours looking at the dual of each block while going back towards the first vectors. The experimental time and quality of SDBKZ are similar to that of BKZ, yet the theoretical analysis is much easier. It provides a more confident way to extrapolate lattice reduction performance to bigger dimensions, which is paramount to establish security level as we shall see below.

Slide reduction

When proving the output quality of LLL, one recovers inequalities of the same flavour as that of Hermite's inequality which states that γ n ≤ � � 4/3 � n-1 . Therefore as Gama and Nguyen put it [START_REF] Gama | Finding short lattice vectors within Mordell's inequality[END_REF], LLL can be viewed as an algorithmic version of Hermite's inequality. This suggests that given another inequality on γ n , it could be possible to derive its algorithmic version. This is exactly what they did with Mordell's inequality, which gives

γ n ≤ γ n-1 k-1 k for 2 ≤ k ≤ n
The resulting algorithm is called Slide Reduction and is another blockwise generalisation of LLL. It also makes a polynomial number of short vector searches and its theoretical analysis is easier than that of BKZ. However the first experimental results did not show attractive speed-ups and it was not used until Micciancio and Walter [START_REF] Micciancio | Practical, predictable lattice basis reduction[END_REF] reinstated it as a good reduction algorithm.

Performances and output qualities

Before comparing the algorithm, we shall have some common quality measure(s).

How to measure a basis quality?

Despite the very visual insight we have in dimension 2, as in Figure 4.1, it is not trivial to have such a clear indicator in arbitrarily large dimensions. We recall here the different criteria used in the literature.

Gram-Schmidt norms and the Geometric Serie Assumption. We saw that the Gram-Schmidt (GS) vectors b � i and coefficients µ i,j play central roles in lattice reduction algorithms. So it is quite natural to look at these vectors for reduced bases, especially their norms �b � i �. In a log-plot, as in Figure 3.5, we see that the decreasing curves can be approximated by a line. This is referred to as the Geometric Series Assumption (GSA) [START_REF] Schnorr | Lattice reduction by random sampling and birthday methods[END_REF] ∀i ∈ {1, . . . , n},

�b � i � = α i-1 �b 1 �, for some α ∈ [0, 1]
We can see throughout a reduction (between BKZ tours for example) that reducing more makes the line closer to the horizontal. α gets closer to 1 and would be 1 in the case of an orthonormal basis.

Root Hermite factor. Without question the most popular indicator is the root Hermite factor, usually noted δ 0 it is defined by

�b 1 � = δ n 0 • Vol(L) 1/n
It essentially captures how small the first vector of the basis is. However, under the GSA, it conveys information on the whole basis. Indeed if we combine the equations, we get

Vol(L) = n � i=1 �b i � = n � i=1 α i-1 �b 1 � = n � i=1 � α i-1 • δ n 0 • Vol(L) 1/n � = � n � i=1 α i-1 � • δ 2n 0 Vol(L)
Hence, α n(n-1)/2 = δ -2n 0 , which yields α ≈ 1/δ 2 0 . Informally, this means that under the GSA, making the first basis vector shorter yields a better basis. Consequently we usually use this root Hermite factor, quite easy to compute, to measure the (whole) basis quality.

The orthogonality defect. Another measure that takes into account the whole basis is the orthogonality defect. This one is about comparing the volume of the lattice with the product of the basis vectors lengths.

od(L) = � n i=1 �b i � Vol(L) = � n i=1 �b i � � n i=1 �b � i �
We can see that od(L) ≥ 1 with equality when the basis is orthogonal.

Half-volume. This other measure captures the balance between the two halves of the basis. It is defined by

V 1/2 (L) = � �n/2� i=1 �b � i � � n i=�n/2�+1 �b � i �
This one is more difficult to compute but can be useful to estimate enumeration times in the reduced basis. Again we would want it to be closest to 1.

Algorithms' complexities and performances

We summarize here the costs of the algorithms presented above, together with the root Hermite factor they achieve. Some results come from proven bounds and theoretical results, other from practical experimental results. When speaking about complexity, we have n the dimension of the lattice (or the basis matrix, we keep the full-rank case) and B is an upper bound of the entries of the matrix, i.e. log B is the size of the entries.

LLL.

The initial LLL proposal has a complexity of O(n 6 log B) and achieves a theoretical quality of δ 0 = (4/3) n-1 4n [START_REF] Klaas Lenstra | Factoring polynomials with rational coefficients[END_REF]. In other words, it is a polynomial time algorithm that achieves an exponential approximation factor. After many improvements [NS05, NS09, NV09], we now have more efficient algorithms that have complexity O(n 5+ε log B + n 4+ε log 2 B). On the implementation side, there are floating-point versions of LLL that run in time O(n 3 log 2 B) [START_REF] Chen | BKZ 2.0: Better lattice security estimates[END_REF]. Also, experimental results showed that LLL can achieve quality as good as δ 0 = 1.021, showing sometimes unexpected performance [START_REF] Nguyen | LLL on the average[END_REF][START_REF] Gama | Predicting lattice reduction[END_REF].

BKZ.

To estimate the execution time of BKZ, we need to consider extra parameters: the number of tours N required for it to converge and the time t β of the local search for short vectors. The overall complexity is then O(N × n × t β ).

While the theoretical upper bound for N is exponential in n [GN08b], heuristic analysis shows that after a polynomial number of tours, namely N = (n/β) 2 log n, the output quality is already very close to what is expected [START_REF] Hanrot | Analyzing blockwise lattice algorithms using dynamical systems[END_REF].

Concerning the cost of the local searches, many studies must be taken into account to provide a correct estimate. There are several approaches to do this: computing the lattice Voronoi cell [MV10], sieving [START_REF] Shi Bai | Tuple lattice sieving[END_REF][START_REF] Herold | Improved algorithms for the approximate k-list problem in euclidean norm[END_REF] or enumerating [START_REF] Fincke | Improved methods for calculating vectors of short length in a lattice, including a complexity analysis[END_REF][START_REF] Gama | Lattice enumeration using extreme pruning[END_REF]. Asymptotically, sieving has the lowest complexity, but as of today enumeration with extreme pruning is the most efficient (to break challenges for example). Sieving and enumeration also differ greatly with respect to memory usage. It is polynomial for enumeration but exponential for sieving. Hence we can use the following for t β

t β =      O(2 Θ(β) )
for sieving

O(2 Θ(β 2 ) )
for enumeration

O(β Θ(β) ) for enumeration with preprocessing

There are other estimates for BKZ running time [START_REF] Lindner | Better key sizes (and attacks) for LWEbased encryption[END_REF][START_REF] Van De Pol | Estimating key sizes for high dimensional lattice-based systems[END_REF], but quite obsolete now that we have a much better understanding of the algorithm.

The theoretical output quality of BKZ is:

δ 0 = � 2γ n-1 2(β-1) +1.5 β � 1 n .
From the work from Chen [Che13], we estimate that the output quality is

δ 0 = � β 2πe • (πβ) 1/β � 1/2(β+1) .
Slide reduction. The theoretical output quality of Slide Reduction is very similar, yet better, than that of BKZ [START_REF] Gama | Finding short lattice vectors within Mordell's inequality[END_REF]:

δ 0 = � 2γ n-1 2(β-1) β � 1 n .
In practice they show similar output quality [START_REF] Micciancio | Practical, predictable lattice basis reduction[END_REF].

In addition, the theoretical complexity analysis guarantees only a polynomial number of local searches whereas for BKZ this comes only as a heuristic result. In practice Slide Reduction behaves like BKZ.

Improving reduction algorithms

We saw in the previous section that lattice reduction performance are central to estimating security of lattice-based schemes. Our cryptanalytic work led us to look under the hood and bring some improvements to lattice reductions, especially around the fplll library. We detail below the work on reductions we did in the course of this thesis.

The fplll days

The fplll library was originated by Stehlé's work a few years ago and is now a collaborative project on GitHub. It brings together several lattice enthusiasts from the cryptology community and is now available from SageMath, thanks to the side project fpylll. fplll stands for "floating-point LLL", it provides several lattice reduction algorithms: floatingpoint LLL versions [START_REF] Phong | An LLL algorithm with quadratic complexity[END_REF] which can be easily used through a wrapper that optimises the floating point settings along the computation, BKZ [SE94] algorithm together with BKZ 2.0 [START_REF] Chen | BKZ 2.0: Better lattice security estimates[END_REF] heuristics and also slide reduction [START_REF] Gama | Finding short lattice vectors within Mordell's inequality[END_REF] and self-dual BKZ [START_REF] Micciancio | Practical, predictable lattice basis reduction[END_REF]. There are also SVP and CVP enumeration routines.

In the same spirit as the Sage Days, the core team of fplll has decided to put in place regular meetings (roughly twice a year) to bring together the maintainers for some days. The objective is to leap forward on evolutions with the relevant people present and to give more visibility to the community. I actively took part in the first two sessions of these fplll days (June and December 2016), my contributions range from CVP routine enhancement to work on the new heuristics for BKZ and are detailed in this section.

Proven CVP

CVP enumeration is more involved than SVP For enumeration, the cases of SVP and CVP are very similar. The objective is to enumerate lattice vectors close to 0 or some target vector t but some subtleties arise when doing floating-point implementations and studying carefully their respective complexities. This issue is discussed in [START_REF] Kannan | Improved algorithms for integer programming and related lattice problems[END_REF][START_REF] Pujol | Recherche efficace de vecteur court dans un réseau euclidien[END_REF].

Let us remember that we want to find a lattice vector v = � n i=1 v i b i ∈ L(B) close to some vector w = � n i=1 t i b � i , where the b � i are the Gram-Schmidt vectors of B. We note r i = �b � i �. We know, assume, or at least want that

�w -v� 2 = � n � i=1 t i b � i - n � i=1 v i b i � 2 = � n � i=1 t i b � i - n � i=1 v i � b � i + n � j=i+1 µ i,j b � j � � 2 = n � i=1 � t i -v i - n � j=i+1 µ j,i v j � 2 r 2 i = n � i=1 � c i -v i � 2 r 2 i , with c i = t i - n � j=i+1 µ j,i v j ≤ R 2 for some radius R ≥ 0
Now the enumeration algorithm works as follows: start at the bottom of the tree i = n and at each depth try all v i such that

(c i -v i ) 2 r 2 i ≤ R 2 - n � j=i+1 (c j -v j ) 2 r 2 j
Since we are going toward decreasing indices, v i is the only variable quantity in the equation above. Also it is an integer, so there is a bounded number of possibilities. We can show that there is a maximum of 2R/r i + 1 possible values.

However, if we want to solve CVP and not BDD, i.e. we do not know R in advance, we need to pick a value for it. In the SVP case, setting R = λ 1 (L) does the trick, but for CVP we need to go to the top of the tree to conclude, which is not the case for SVP. So it is likely that, even for the correct solution, the bound at depth 1 < i < n will discard the current candidate. So we need to have at least R ≥ � n i=1 r 2 i /4. This bound is not satisfactory either. Indeed, the Geometric Series Assumption tells us that for a reduced basis, the r i are decreasing. But there are cases, that can be exhibited, for which the suite is arbitrarily increasing. For such case, the present approach that enumerates 2R/r i + 1 solution per level is likely to waste enormous amount of time. So we need to do better.

Fixing fplll

The algorithmic solution to this is to somehow reset the enumeration when we reach a r i with maximal value before going deeper in the tree. It improves both the running time and the numerical stability (for floating-point implementations). The fplll routine for CVP was not using this trick, that is why it was flagged "experimental". During the first fplll days, we implemented it with some help from Marc Stevens. This idea is to separate the depths into the largest intervals in which the r i are decreasing. Say it is decreasing from i = 1 to i 0 -1 for some i 0 > 1 and from i 0 to n. Below i 0 , it makes sense to set R = � n i=i 0 r i /4 ≤ (ni 0 )r 0 /4 but for depth between 1 and i 0 -1, the number of candidates at each depth is probably going to be huge, so it would be better to set the bound differently. At this point, we have some candidates for the last components of v = (�, . . . , �, v i 0 , . . . , v n ) and we still want to find the firsts. Remember that at this point, our objective is �w -

� i 0 -1 � i=1 v i b i + n � i=i 0 v i b i � � 2 ≤ R 2
We can view this as a new CVP in dimension i 0 -1 where the new target is w -

� n i=i 0 v i b i . Moreover, instead of going on with a bound R �2 = R 2 - � n i=i 0 (c i -v i ) 2 r 2 i , we can pick R �2 = � i 0 -1 i=1 (c i -v i ) 2 r 2 i .
In the possible cases where the r i have different sizes, this approach also improves numerical stability, because where R � would have been of the order of R, i.e. too big, R � depends only on the "small" r i and will be more adapted.

The code to add this reset feature was integrated to fplll1 . It involved patching most of the enumeration routines.

BKZ 3

During the second fplll days, we worked together with Léo Ducas and Martin Albrecht on new ways to make BKZ reduction faster. We refer to this as YoloBKZ or more pompously BKZ 3. We shall now first review the BKZ algorithm in details, together with BKZ 2.0 heuristics and then introduce our new techniques.

Review of BKZ and BKZ 2.0

We briefly said that BKZ was a blockwise algorithm performing several tours on the basis, using a shifting window called a block. For each position of this block, the local basis is improved with the addition of a newly found short vector. The output quality of BKZ depends mainly on the block-size β. So does its time complexity, which is also dependent on the number of tours. BKZ, was first introduced by Schnorr and Euchner [START_REF] Schnorr | Lattice basis reduction: Improved practical algorithms and solving subset sum problems[END_REF] and refined by Chen and Nguyen [START_REF] Chen | BKZ 2.0: Better lattice security estimates[END_REF] who brought several tweaks to make it faster.

More precisely, BKZ algorithm works as described in Algorithm 4.1. We keep a high level description here to focus on the essential aspects. The interested reader can also have a look at an implementation of BKZ in fpylll2 No progress is made. The termination condition of BKZ in its original version says that the algorithm should continue as long as the basis is changed during a tour, i.e. a shorter vector is found in at least one of the blocks. It is proven that BKZ terminates, and observed that the number of tours is exponential (in the lattice dimension and size of its entries) [START_REF] Gama | Predicting lattice reduction[END_REF]. A heuristic result [START_REF] Hanrot | Analyzing blockwise lattice algorithms using dynamical systems[END_REF] suggests however that it should be enough to perform a polynomial number of tours to get an output quality close to final. This is what we call the early abort strategy. BKZ is stopped when no "significant" progress is made on a tour. In practice, the GSA slope is monitored and if the progress per tour is below some threshold for some number of tours in a row, the algorithm is stopped.

FindSVP. This SVP oracle may be implemented using techniques we mentioned above: sieving or enumeration. Recent works on sieving [BTS16, HK17, BDGL16] bring it closer to be best in practice, but for a long time enumeration wan out. Most of the heuristics that shape BKZ 2.0 are about optimising enumeration. In fplll, enumeration is used, yet the fplll days 4 in December 2017 are about bringing in the latest algorithmic improvements on sieving.

With enumeration there is always the question about the enumeration radius. As we are doing SVP we do not have the subtleties of CVP to take care of as in the previous section. We can set R = �b � j �, at least the enumeration will output this vector. Yet the Gaussian Heuristic also provides some clue on how short we expect the vector to be. So in practice, the enumeration radius is set to what is minimal between �b � j � and 1.05 times the Gaussian Heuristic prediction. Also, as for any enumeration, the pruning function should be chosen to minimize the overall enumeration, even if it implies to perform many cheap enumerations with low success probability on different bases (obtained by randomisation). Now that we did our best to have a very efficient enumeration, we shall not forget about the quality of the local basis. By design, the BKZ algorithm is such that any block is LLL-reduced when FindSVP is called. LLL-reduced bases offer only fair context to run enumeration, the situation can be improved if we have BKZ-reduced bases. So this is exactly what is done: in the case of a BKZ-β reduction, it is very appropriate to have the local bases BKZ-β � reduced, for some β � < β. Optimising the choices for β � in terms of β has been addressed by Chen and Nguyen when they introduced BKZ 2.0. We shall come back to this later. We also call this step the SVP pre-processing step.

fplll is distributed with a default strategy that provides "optimised" choices for preprocessing block-sizes, enumeration radiuses and pruning function, depending on the requested BKZ reduction. This strategy shows good results, yet it is established from average reduction behaviour on generic lattices, so it may be sub-optimal for some particular lattices.

If v is useful. The FindSVP oracle should at least return a vector as good as the first of the local basis. If it is the case and not better, there is obviously no need for insertion. BKZ and BKZ 2.0 both share this behaviour.

Insert v into B. When inserting a new vector, the local basis momentarily gets an extra vector. The solution to remove the linear dependencies and to keep the best vectors is to run LLL. This is usually done on the beginning of the whole basis, between indices 1 and k + 1. We refer to this insertion and reduction step as the SVP post-processing step.

Introducing new heuristics

We present now some new tricks for faster BKZ. This is mainly experimental and not yet published in final versions. It results from manual experiments and tunings and extensively benefits from the flexibility of fpylll.

Auto-adaptive pre-processing. Instead of using pre-computed strategies, it would be best to have an adaptive strategy. The same wish extends to all parameters of lattice reduction, of course. Yet for pre-preprocessing Léo Ducas developed some code which monitors the enumeration behaviour (success probability and number of enumerated nodes) to adapt on-the-fly the pre-processing settings that will be used for the next block. We ran several experiments to try to get a trend on how it behaves. This aim was to derive a pre-computed dynamic strategy or strategies. But as we can see in Figure 4.2, it changes completely from one lattice to the other, alternating phases of small and big block-sizes.

In the end, it makes it faster to reach a BKZ 2.0 quality.

Tentative multiple insertions.

The time spent in the FindSVP oracle is a significant part of the total reduction time. Yet each call is worth, at most, one short vector. We investigated the possibility to make use of other candidates, encountered during the enumeration (or sieving). For example, we may wish to insert not only the shortest vector found but maybe also the second shortest or more. The post-processing step will automatically handle insertions of many vectors thanks to the LLL behaviour which will keep only β linearly independent vectors. Consequently, we modified the enumeration procedure in fplll to enable the return of more than one vector, and tried to do more than one insertion per block. We explored inserting 2 vectors, 5 vectors, or β/2 or β/4. None of these strategies improved the quality or the speed. Dead end.

Weaker/less LLL in post-processing. Here we want to decrease the time spent in LLL in the post-processing. First, the vector returned by FindSVP may be easy to insert manually into the basis. So there is some code to handle such cases, like when the vector has only ±1 coordinates. Next, running a very weak LLL is enough to remove linear dependencies. Though, next time we work in the block, we want it to be reduced enough for the next FindSVP call to work fine. So two options: reducing not to weakly (η = 0.71 gives good results) or split the work between the current post-processing and the next pre-processing (of this same block, i.e. in the next tour). Second option offers even more possibilities. For example, reducing only parts of the basis before going to the next block, the rest of the work will be done later if needed.

Several leads have been followed independently by Martin, Damien, Léo, Shi, Marc and myself but the techniques are not orthogonal and not necessarily compatible. Below we report some speed-ups between BKZ 2.0 and BKZ including such heuristics. The one we keep from this section is that of using weak LLL with η = 0.71.

Progressive block-sizes. Similarly as we use locally BKZ with smaller block-size to speed up enumeration in blocks, we may BKZ-reduce the whole basis with a smaller block-size 4.1 -Time and quality improvements of a ramp-up phase before doing the reduction with the block-size we want. This trend has already appeared in the literature and studied recently [HRP13, AWHT16]. The later work proposes very clever techniques to simulate the best progression toward a target block-size. We adopted a more down-to-earth approach, based on experiments.

Our technique relies solely on a ramp-up phase, prior to the normal BKZ execution. From a practical point of view, on a lattice of dimension 160, BKZ reductions for block-size under 40 are of negligible costs, whereas the closer we get to the target block-size, the less negligible it becomes. So our idea for ramp-up was to jump by a step of 10 until β -10 and then β -5, doing one BKZ tour for each block-size.

The results are quite impressive (cf. Table 4.1 and Figure 4.3): the ramp-up phase takes about 75 % of one normal tour and the quality after ramp-up and one tour is the same as the quality after doing 3 tours directly. So we have a speed-up from 3 to 1.75 just with this naive technique. Further into the reduction, as the normal tours happen, the benefits of this ramp-up, independently of its nature, fade away. Considering the results, this technique should also be put in place for all local pre-processing BKZ. This would bring speed-ups for the whole BKZ reduction and even in this naive, costless fashion.

2-phases LLL

We made another observation on LLL behaviour during the many experiments we conducted. On average and on our lattices from embeddings, it seems faster to first run a weak LLL reduction, before running the one with our target parameters. We did not investigate a lot, but Figure 4.4 shows that it can make the reduction up to two times faster. Damien Stehlé pointed us that this strategy was already mentioned [START_REF] Cohen | A Course in Computational Algebraic Number Theory[END_REF].

Conclusion

We reported here several experimental results on lattice reduction algorithms and our contributions to fplll. Interestingly, the ramp-up paradigm seems efficient for both BKZ and LLL algorithm so could be studied more closely. Many heuristics drive the concrete performances of the lattice reduction algorithms, so there are still many hindsights to gain before being able to extrapolate confidently their performances. Also the days of enumeration may soon be over since we see many speedups coming from sieving and its new tricks.

The great discussion within the fplll community allowed us to contribute to the long existing field of computational cryptanalysis. Standing between what theorems prove and what computers can do, the landscape of the contribution is of the most exciting. The progresses we helped making bring more confidence to the whole lattice based cryptography community. This is paramount to evolve towards broader acceptation and use of these primitives.

In the beginning of this thesis, we started by working on the cryptanalytic or attack side. Now we can safely head to the task of implementing homomorphic encryption schemes, for real. Considering the state-of-the-art on the existing schemes in 2015, the challenge for us is about choosing parameters for them to ensure both correctness of our computations and enough security. The insights we got from our previous works allow us to confidently address this topic.

In this chapter we shall first review the classical parameter derivation methods. Then, we present a common work with Vincent Migliore whose aim is to provide ready-to-use content for people from outside the cryptography community, e.g. implementers. In the end we also present some results on the influence of the error size over the other parameters.

Most of this work was accepted for a special issue of IEEE Transactions on computers on Cryptographic Engineering in a Post-Quantum World [?].

Review of the methods

Prior to our study, several works had already be done on scheme analysis and comparison. First, a comparison of FV and YASHE' from Lepoint and Naehrig [START_REF] Lepoint | A comparison of the homomorphic encryption schemes FV and YASHE[END_REF]. They derived parameters for both schemes, implemented them in C++ and compared their performances at evaluating a lightweight block cipher SIMON [BTCS + 15]. They established that the noise growth in FV is smaller than in YASHE', while the latter turned out to be faster. Later, Costache and Smart [START_REF] Costache | Which ring based somewhat homomorphic encryption scheme is best?[END_REF] included BGV. They compared BGV, FV and YASHE' and highlighted the main advantages of each of them, namely BGV is best for large plaintext moduli, and YASHE' wins in other cases.

At the heart of a comparative parameter selection stand two main challenges. The first one is to have a unified description of the schemes, so that when we write equations about the noise growth, i.e. about the correctness of the scheme, we handle comparable data. And secondly, there is a need to draw parameters that achieve the same security level for all schemes.

Addressing the first challenge is just a matter of putting the operations into perspective to unify the different actions done to the ciphertexts. Both previous works and ours do that. However when it comes to security, we saw in the previous chapters that huge efforts are being done on the attack front and it can be difficult to confidently draw parameters. As it turns out that YASHE' has been broken, the outcomes of both previous studies should be revised. We remind that [START_REF] Lepoint | A comparison of the homomorphic encryption schemes FV and YASHE[END_REF] uses the technique from [START_REF] Van De Pol | Estimating key sizes for high dimensional lattice-based systems[END_REF] and [START_REF] Costache | Which ring based somewhat homomorphic encryption scheme is best?[END_REF] uses that of [START_REF] Lindner | Better key sizes (and attacks) for LWEbased encryption[END_REF]. Both techniques attempt to model the power of lattice reduction at solving LWE from only one point of view. However, YASHE' is an efficient variant of YASHE, which was not proven secure, and these models could not account for an attack such as the sublattice attack.

Comparing FV and SHIELD

Now we present our comparative study of somewhat homomorphic schemes: the schemes included, the use cases. Then we present both FV and SHIELD in our unified presentation and derive their noise growth equations (for scheme correctness) and then we detail the security aspects. The section after documents our findings. , so we had originally included them in the scope of our comparative study, but we dropped them later. The attack broke the security assumptions of both YASHE' and F-NTRU. YASHE is still secure but impractical and for F-NTRU the correctness and security constraints can no longer be satisfied.

BGV differs significantly from FV and SHIELD, by its structure involving several moduli. So with hardware considerations in mind, we decided not to include it in our work. Accelerating hardware modular reduction with changing modulus seemed quite a challenge and not promising for performance. Nonetheless, BGV is a good candidate, especially when it comes to large plaintext moduli [GHS12b, CSVW16, JA16, CKKS17]. Several works also support the use of binary plaintext. Among other things, it enables more complex operators such as comparison. Hence our choice for FV and SHIELD.

Use cases

Our work aims at comparing FV and SHIELD on different scenarios. The main aspect we consider for comparison is the size of the ciphertexts and key materials, because the costs of the communications and homomorphic operations will then depend directly on them. So we study the parameters in the following cases:

• Evaluation of an arbitrary binary circuit of depth L, i.e. a polynomial for maximum degree 2 L (see Figure 5.1a).

• Evaluation of an optimised binary circuit of degree L (see Figure 5.1b). With SHIELD the noise growth is better when a multiplication occurs with a "fresh" ciphertext (i.e. depth L with one additional multiplication per level). So we highlight the parameters of this optimal case.

• Use of NTT multiplication in the Negative Wrapped Convolution regime. This setting saves a polynomial reduction when doing a multiplication, but implies extra constraints on the dimension n. With high performance objectives it could be interesting to work in this regime, so we study the impact on these extra constraints on the other parameters.

• Batching or Single Instruction on Multiple Data (SIMD) technique. This trick allows to amortise the computation cost by evaluating the same circuit on several different input data. For this, we also studied the choice of dimensions which yield different numbers of possible slots. This was mostly done by Vincent.

Unified presentation

To begin this comparative work, we present FV and SHIELD (and did also F-NTRU at the beginning) in a somewhat unified formalism.

FV

To detail the brief presentation that we made of FV in a previous chapter, we state in detail the sub-routines of the scheme from Fan-Vercauteren. We note l ω,q = �log 2 q/ log 2 ω�. Algorithm 5.1 introduces utility functions, Alg. 5.2 the key generation procedures, Alg.

SHIELD

Now we introduce, under the same formalism, the subroutines of SHIELD. We note N = 2 × �log 2 q�. For a ring element a we use a (j) to speak about the ring element composed of the j-th bit(s) of a. Algorithm 5.5 introduces utility functions, Alg. 5.6 the key generation procedures, Alg. 5.7 the usual encryption and decryption and Alg. 5.8 presents the actual homomorphic elementary operations. As the names suggest BitDecompInv is the invert function of BitDecomp. We call them BD and BDI for conciseness.

Noise growth equations

Next, under this unified framework we derive the noise growth equations for both schemes. Indeed, to control correctness one expresses the noise after L multiplications and validates that a decryption of a ciphertext with this amount of noise will yield the expected plaintext. This work has to be done for each scheme.

Algorithm 5.1 FV: Utility functions

1: function FV.PowersOf ω,q (a ∈ R q )

2:

A = (A 0 , • • • , A lω,q-1 ) ∈ R lω,q q 3:
for i = 0 to l ω,q -1 do 4:

A i ← [a • ω i ] q 5:
end for 6:

return A 7: end function 8: function FV.WordDecomp ω,q (a ∈ R q ) 9:

A = (A 0 , • • • , A lω,q-1 ) ∈ R lω,q q 10:
for i = 0 to l ω,q -1 do 11:

l 0 = i × log 2 ω 12: l 1 = (i + 1) × log 2 ω -1 13: A i ← a (l 0 •••l 1 ) 14:
p k ← (-a • s + e, a)
6:

s k ← s 7: return (p k , s k ) 8: end function 9: function FV.GenRelinKeys(p k , s k , σ err ) 10: A ← U lω,q Rq 11: E ← D lω,q Rq,σerr 12: γ ← � � FV.PowersOf ω,q � s 2 k � - � A • s k + E � � q , A � 13:
return γ 14: end function

c ← � � q/t × m + p k,0 u + e 1 � q , � p k,1 u + e 2 � q � 5:
return c 6: end function 7: function FV.Decrypt(c, s k ) for j = 0 to log 2 q -1 do 5:

8: � m ← � c 0 + c 1 • s k � q 9: m = � � m × t/q�
� c 0 ← [�c 0 a × c 0 b × t/q�] q 7: � c 1 ← [�(c 0 a × c 1 b + c 1 a × c 0 b ) × t/q�] q 8: � c 2 ← [�c 1 a × c 1 b × t/q�] q 9: c × ← FV.Relin(� c 0 , � c 1 , � c 2 , γ) 10: return c × 11: end function 12: function FV.Relin(� c 0 , � c 1 , � c 2 , γ) 13: c 0 ← [� c 0 + � FV.WordDecomp ω,q (� c 2 ), γ 0 �] q 14: c 1 ← [� c 1 + � FV.WordDecomp ω,q (� c 2 ), γ 1 �] q
B i,j ← A (j) i,0 6: B i,j+log 2 q ← A (j) i,
A ∈ R N ×2 q 13: for i = 0 to N -1 do 14: A i,0 ← � log 2 q-1 j=0 2 j • B i,j 15: A i,1 ← � N -1 j=log 2 q 2 j • B i
P k = � b a � 7: S k = � 1 -t � 8: return (P k , S k ) ∈ R 1×2 q × R 2×1
C × = BitDecomp(C a ) × C b 7:
return C × 8: end function On the security front, a unique common work is needed. At first we went in a similar fashion as Lepoint and Naehrig did in their comparative study of FV and YASHE that had been used several times by implementers.

Notation

We briefly introduce additional notation for the noise extraction. When a ← D Rq,σ key and b ← D Rq,σerr , we note �a� ∞ = B key and �b� ∞ = B err . B 0 refers to the upper bound of the noise for a fresh ciphertext, B L denotes the noise bound after a multiplicative depth of L. We also introduce the expansion factor δ R of a ring R, which bounds the product of two ring elements. The expansion can be expressed as

δ R = sup a,b∈R � �a • b� ∞ �a� ∞ �b� ∞ � FV
The noise bound has been thoroughly studied in [START_REF] Lepoint | A comparison of the homomorphic encryption schemes FV and YASHE[END_REF], thus we only recall some key aspects below.

Initial noise. To determine the initial noise, we apply the decryption procedure on a fresh ciphertext, focusing on the encryption of a 0: c 0 + c 1 s = (-as + e)u + e 1 + (au + e 2 )s = eu + e 1 + e 2 s Thus, the initial noise is B 0 = B err (1 + 2nB key ).

Multiplicative noise. Following the approach in [LN14, Section 3.5] we can express an inequality that must be satisfied for decryption to be correct at depth L.

C L 1 B 0 + LC L-1 1 C 2 < (�q/t� -(q -Δt))/2
where

C 1 = δt(4 + δB key ), C 2 = δ 2 B key (B key + t 2 ) + δωl ω,q B err
For binary messages it becomes:

C 1 = 2n(4 + nB key ), C 2 = n 2 B key (B key + 4) + nωl ω,q B err

SHIELD

The authors of [START_REF] Khedr | SHIELD: scalable homomorphic implementation of encrypted data-classifiers[END_REF] only provided an asymptotic evaluation of SHIELD noise growth.

Following the same approach as before, we develop below a more precise calculation, providing the constant terms.

Initial noise. To determine the initial noise, we apply the decryption procedure on a fresh ciphertext, focusing on the encryption of a 0:

C • S k = (m • BDI(I N ) + r N×1 • P k + E N×2 ) • S k = r N×1 • P k • S k + E N×2 • S k
We set E = r N×1 • P k • S k + E N×2 • S key and we have

�E[i]� ∞ ≤ nB err + B err + n • B err • B key = B err (1 + n(1 + B key ))
Thus, the initial noise can be bounded by

B 0 = B err (1 + n(1 + B key )).
Multiplicative noise. To determine the noise after a homomorphic multiplication in SHIELD, we apply the decryption procedure after the multiplication step. Recall that

SHIELD.Mult(C a , C b ) = BD(C a ) • C b BD(C a ) • C b • S k = BD(C a )(m b BDI(I N ) • S k + E b ) = m b • BD(C a ) • BDI(I N ) • S k + BD(C a ) • E b = m b • C a • S k + BD(C a ) • E b = m a • m b • BDI(I N ) • S k + m b • E a + BD(C a ) • E b We set E × = m b • E a + BD(C a ) • E b .
To bound E × , which is a vector, one must bound each elements. BD(C a ) is always a N × N -matrix of binary polynomials. Thus, each row of BD(C a ) • E b is a product/accumulation of N = 2 log 2 q binary polynomials with polynomials bounded by �E b [i]� ∞ . After one homomorphic multiplication, the noise can be bounded by

�E × [i]� ∞ ≤ m a • B a 0 + 2n • log 2 q • B b 0 ≤ B 0 (1 + 2n • log 2 q) (5.1)
Then, by an immediate induction, the noise after L homomorphic multiplications can be expressed as B L = B 0 (1 + 2n log 2 q) L . To be able to decrypt without error after L homomorphic multiplications, the final noise must be lower than q/2. We must have q/2 > B 0 (1 + 2n log 2 q) L Better noise for multiplication. Unlike in FV, noise in SHIELD grows slowly if a ciphertext is multiplied by a fresh one. By carefully examining Equation 5.1, one can deduce that the noise of each ciphertext is independent. Thus, the multiplicative noise growth can be more finely managed. When a ciphertext is multiplied by L other fresh ciphertexts, the noise growth can be expressed as With batching. Earlier, we extracted noise parameters when m ∈ {0, 1}. However, if one wants to use batch operations, the message is now a polynomial with coefficients in {0, 1}.

B L = B 0 + L(2n log 2 q)B 0 = B 0 (1 + 2Ln log 2 q)
This has a significant impact on the noise growth in SHIELD. We express the new bound of the noise E × :

�E × [i]� ∞ ≤ �m b • E a � ∞ + �BD(C a ) • E b � ∞ ≤ n • �m b � ∞ �E a � ∞ + 2n • log 2 q • �E b � ∞
In the case of the optimised circuit for SHIELD, i.e. the second ciphertext is a fresh one, the noise new bound can be expressed as :

B i+1 = n • B i + 2n • log 2 q • B 0 It is an arithmetico-geometric sequence of the form B i+1 = a • B i + b, where a = n and b = 2n log 2 qB 0 . So B L = a L (B 0 -r) + r, with r = b 1-a .

Security

While the noise management determines the multiplicative depth and set a minimum q to keep computations correct, the security requirement asks for the opposite. It upper-bounds the size of the modulus for a given dimension n. This means that, sometimes, to ensure a given multiplicative depth one cannot only increase the modulus. The induced loss in security must be compensated by an increase in the dimension n. For a brief overview we put in Table 5.1 the maximal allowed log q for several dimensions at 80 and 128 bits of security.

As expected in cryptography, all the schemes presented here come with hardness results, provided by reductions to the Ring-LWE problem. This hard problem is one of the best candidates for post-quantum cryptography. There are no quantum attacks performing better than the classical ones. Yet, beyond these asymptotic reductions, we need concrete hardness results to choose the scheme parameters according to a security level objective, e.g. 80 bits or 128 bits. As we said above, one key component to make a pertinent study is to have all the schemes secure, and equally secure. Consequently, we focus our study on parameters that do not violate the security reductions. First and foremost is the error distribution, which should not be too small with respect to the dimension n [Reg05]. Both previous studies did not make this similar choice.

At first we tried to adapt and update the lattice reduction modelling as in [START_REF] Lepoint | A comparison of the homomorphic encryption schemes FV and YASHE[END_REF] but we quickly shifted to the lwe-estimator from Albrecht [Albb]. We extensively discuss this matter in the previous chapters of the manuscript. The take-away conclusion is that the estimator from Albrecht is being constantly updated with the publications about attack improvements and as of today could be used as a very good indicator for the security level of a given parameter set.

To produce the values for this study, we used it as is in commit 61ac716, setting our threshold at exactly 80 or 128 bits of security. For real applications with long term perspective, we advice to add some extra bits of margin. We already said it several times, huge efforts are conducted nowadays on cryptanalysis of post-quantum cryptography and new attacks can take away bits of security faster than Moore's Law.

Parameters in perspective

We automated the parameter derivation with scripts, under Matlab first. Then we moved to Sage to directly use Albrecht's estimator as a black-box. This allows to conveniently generate up-to-date values. In this section, we explore different settings: arbitrary circuit, optimised circuit, NWC, batching, and report concrete parameters for scheme comparison.

How to proceed? Real use-cases of homomorphic cryptography define requirements for the multiplicative depth L and a security level λ to achieve, then one needs to choose the corresponding security parameters. However we have three variables to adjust: the dimension n, the modulus q and the error size σ. Plus, a change to one of them could be compensated, amplified or cancelled by a change to another one, so we had to establish a sound procedure to avoid being caught in loops or achieving suboptimal parameters.

To remove one degree of freedom to the system, we decided to go for a fixed error size and set it to σ = 2 √ n. This choice is compliant with the hardness reduction and a bigger error would have a negative impact on the correctness. At least this is what is usually believed in, but we present in the next section how this is not always true, on average it seems a correct assumption. So, the procedure goes as follows: for a tentative dimension n (start small), derive a lower bound for the modulus q to ensure correctness. Check if this lower bound is small enough so that with this dimension n (and σ), the security is good enough. If it is, the triplet (n, q, σ) satisfies both correctness and security requirements; if not, try again to find a modulus, this time with a bigger n. We formalize this procedure in Algorithm 5.9. The procedure MinModulus involves the noise growth equations established previously and SecurityLevel is a call of Albrecht's estimator.

Multiplicative depth for an arbitrary binary circuit

Table 5.2 provides parameters for FV and SHIELD for 80 and 128 bits of security. They are extracted in the proven-hardness regime, that is to say σ err = 2 √ n for each scheme.

Values for SHIELD seem the best in the tables. However the number of sub-polynomials for a given ciphertext explodes because it is proportional to log 2 q for SHIELD. For example, with L = 5, a ciphertext in SHIELD contains 2 × N = 4 × log 2 q = 480 polynomials of degree-2772 with 120 bits coefficients, whereas in FV a ciphertext is only two polynomials Algorithm 5.9 Determine (n, σ and q) parameters from (L, λ) for a given scheme

1: function ChooseParam(scheme, L, λ) 2: n ← 0 3: repeat 4: n ← n + 1 5: σ ← 2 √ n 6:
q ← MinModulus(n, L, scheme)

7:
until SecurityLevel(n, σ, q) > λ 8:

return n, σ, q 9: end function Table 5.2 -Parameters for FV and SHIELD, where λ is the security level and L the multiplicative depth. Arbitrary circuit. L λ = 80 bits λ = 128 bits ω = 32 bits ω = 64 bits ω = 32 bits ω = 64 bits of degree-3711 with 159 bits coefficients. Consequently, in the case of an arbitrary binary circuit, FV is best.

log 2 q n log 2 q n log 2 q n log 2 q n 1 54

Multiplicative depth for an optimised circuit

As stated in the previous section, SHIELD seems very costly for arbitrary circuits. However, all third generation schemes have a really interesting feature: when a ciphertext is multiplied by a fresh ciphertext, the noise growth is additive instead of multiplicative for binary messages. Table 5.3 provides parameters for SHIELD for such optimised circuit. FV is omitted here, because it presents no particular optimisation. Results are very impressive, SHIELD scales to large multiplicative degree with nearly no impact on n and q. For 80 bits of security, the modulus only increases by 5 bits between a multiplicative depth of 1 and 20 when the degree of the associated cyclotomic polynomial remains under 1024. As a reminder from Table 5.2, FV requires at least n = 14405 and log 2 q = 611 bits for a multiplicative depth of 20.

SHIELD is clearly better than FV in this setting, which is not about evaluating circuit of depth L for all inputs, yet still a degree-L function.

The case of the Negative Wrapped Convolution

As we saw in the tables so far, implementing homomorphic schemes requires to handle polynomials of very high degree with large coefficients. A challenge that arises is that of polynomial multiplication.

More on polynomial multiplication techniques

Recall that there are three families of algorithms for that:

• The schoolbook algorithm which has an asymptotic complexity of O(n 2 )

• More advanced algorithms like Karatsuba-Ofman [START_REF] Karatsuba | Multiplication of multidigit numbers on automata[END_REF] or Toom-Cook [START_REF] Toom | The complexity of a scheme of functional elements realizing the multiplication of integers[END_REF] which have asymptotic complexities of O(n 1.58 ) and O(n 1.465 ) respectively

• And Fast Fourier Transform (FFT) algorithms with the best asymptotic complexity of O(n log n).

The final choice on the polynomial multiplication algorithm will greatly depend on the size of operands and on the constraints from the evaluating environment (software/hardware).

For polynomials with integer modular arithmetic, FFT can be replaced by a specific Number Theoretic Transform (NTT) algorithm. This is a specialisation of the FFT in finite fields, implying only modular integer arithmetic with a prime modulus q instead of complex numbers in FFT. We recall the formal definition of NTT:

Let N be a power of 2, q a prime modulus such as q ≡ 1 mod 2N , and w be a primitive N th root of unity in Z q . The NTT/iNTT of a given polynomial a = (a 0 , • • • , a N -1 ) is defined by:

NTT(a) = � N -1 � j=0 a j w ij � 0≤i≤N -1 iNTT(â) = � n -1 N -1 � j=0 âj w -ij � 0≤i≤N -1
For two polynomials a and b, the polynomial multiplication can be computed as follows:

iNTT(NTT(a) � NTT(b)) = a • b mod X N -1
where � denotes the component-wise multiplication of two vectors. This version NTT is called Positive Wrapped Convolution (PWC) and is not perfectly suited for homomorphic encryption because X N -1 is not a cyclotomic polynomial. Indeed, we do not want the polynomial reduction by X N -1, so we must double the size of the NTT and then perform the polynomial modular reduction manually.

Yet, with a minor modification, the NTT can be turned a Negative Wrapped Convolution (NWC) which computes a•b mod X N +1. Then, because X N +1 is a cyclotomic polynomial, the polynomial modular reduction is directly integrated during NTT computations, at no extra cost.

However, the NWC technique is incompatible with batching as we shall see below. When factoring X n + 1 in Z 2 [X], the resulting polynomial is (X + 1) N , which has a unique factor, namely (X + 1), so it is not possible to "pack" several messages. This is incompatible with the batching technique presented in Section 5. 3.4. Thus, for binary messages, the NWC, which is optimised for performance, is not well suited for parallel computations. For non binary messages, it would be possible to find some configurations compatible with batching by selecting a particular modulus prime q.

Parameters under NTT NWC constraints

We provide in Table 5.4 the parameters for FV and SHIELD under the constraints from NWC. Parameters are selected to maximize the multiplicative depth for a given n, which is necessarily a power of 2, because the NWC NTT set the cyclotomic polynomial to X n + 1. When compared to the previous case, this slightly increases the size of the modulus, for a given multiplicative depth.

For example with FV, for a multiplicative depth of 4, optimised parameters are n = 3065 and log 2 q = 132. In a NWC NTT scenario, new parameters are n = 4096 and log 2 q = 135 bits. Thus, the ciphertexts are slightly larger when compared to optimised ones, but the computation time will be better than with a NTT multiplication of size 2N .

For SHIELD, parameters seem quite independent of the multiplicative depth. Because the polynomial degree is oversized due to NWC, a security of λ = 80 bits requires n = 1024, cf Table 5.3, and we can then go to very high depth. Similarly, n = 2048 is required for λ = 128 bits. n λ = 80 bits λ = 128 bits ω = 32 bits ω = 64 bits ω = 32 bits ω = 64 bits

log 2 q L log 2 q L log 2 q L log 2 q L 2048 79

Parameters for batching

How does it works?

For both FV and SHIELD, the plaintext is a polynomial in R t for some integer t ≥ 2. Because of the expansion of homomorphic encryption, we would like to have integer messages, i.e. t >> 2. However, this integer representation prevents us from doing interesting homomorphic operations. Indeed, all algorithms doing comparison require dealing with binary messages. This latter representation also has some drawbacks. First, to perform an integer addition or multiplication on an integer, one must reconstruct the binary circuit of these operators. Second, the size of ciphertexts is strongly impacted because a ciphertext holds only one bit of plaintext, unlike with integer representation where tens of plaintext bits get encrypted into one ciphertext. Yet, recent research [START_REF] Jäschke | Finite) Field Work: Choosing the Best Encoding of Numbers for FHE Computation[END_REF] demonstrates that using a binary encoding for plaintext data is optimal.

To control the ciphertext expansion issue, the batching technique was introduced [SV14]. This trick allows to "pack" several messages into one single ciphertext. To do so, the associated cyclotomic polynomial must be reducible in Z 2 [X]. Then, a polynomial CRT is applied to pack the messages, with one message per factor.

New parameters for SHIELD

As stated above, the batching technique is very useful to reduce the ciphertext expansion. Table 5.5 provides parameters for SHIELD when the batching technique is used, in an Table 5.5 -Parameters of SHIELD for 80 bits of security when batching is enabled, where λ is the security level and L the multiplicative depth. Binary key, σ err = 2 √ n. optimised circuit as described in Section 5. 3.2. FV is not represented because batching does not imply new noise growth equations as SHIELD. For FV, we detail below the precise choices for n depending on the number of slots.

Unlike when the messages are binary, SHIELD parameters becomes sensitive to the multiplicative depth. As early as depth 3, the dimension goes over 1024 and implies an associated NTT of size 2048. Moreover, the modulus q grows significantly with the depth, on average 12 more bits per level which leads to more and more polynomials for a given ciphertext. For a multiplicative depth of 10, SHIELD with batching requires 596 polynomials of degree 3476 with coefficients of 149 bits, while without batching it only requires 160 polynomials of degree 849 with coefficients of 40 bits. The use of batching with SHIELD is not recommended.

Focus on polynomials choice for batching with FV

For completeness we keep this section though it is based on work from Vincent Migliore only.

We have investigated the structure and the repartition of cyclotomic polynomials in order to measure the practicality of batching. Because there is no known efficient NTT to perform polynomial modular reduction with arbitrary cyclotomic polynomial (apart from the cases of NWC with X n + 1 as presented in Section 5. 3.3), the polynomial modular reduction must be implemented manually. Thus, batching can only be practical if we have a cyclotomic polynomial that allows efficient reduction.

Because the polynomial modular reduction complexity is closely related to the Hamming weight of the cyclotomic polynomial (i.e. the number of non-zero monomials), we have minimised as much as possible this parameter. Table 5.6 provides the conclusions of our exploration. We only have investigated batching for FV, since SHIELD does not seem practical for batching as discussed above. For each multiplicative depth, we have extracted the four cyclotomic polynomials with the lowest Hamming weight and compatible with batching. As can be seen, batching can be implemented for each multiplicative depth with various number of batches. In addition, for all parameters, the Hamming weight is very small when compared to the degree of the cyclotomic polynomial, further supporting the practicality of batching.

Keys and ciphertexts sizes

One of the key aspect for the practicality of homomorphic encryption is obviously the size of keys and ciphertexts. In order to fairly evaluate FV and SHIELD, we have compared the volume of data required for each scheme in a scenario requiring 8 bits of information. Figure 5.2 provides the conclusions of the study. For FV, the size of relinearisation keys are also included because they are required during the homomorphic multiplication. For small multiplicative depths, namely under 8, FV requires a lower amount of data than SHIELD. This is because SHIELD requires large parameters as of the first multiplicative depths. But for larger depths, the improved noise management of SHIELD is highly beneficial. The main issue for FV is the size of the relinearisation key. For a multiplicative depth of 15, it is as large as 17.8 MB, when SHIELD does not require such a key. It can be reduced a bit by enlarging ω at an additional computation cost.

We deepen our analysis on the size of the relinearisation key. In Fig. 5.3a and 5.3b, we show for FV the respective sizes of this additional key and 8 ciphertexts. Both are transmitted from client to server, and we can see that going from ω = 32 to ω = 64 significantly decreases the relinearisation key sizes, and with it, the transmission overhead. We shall also note that when the server sends a computation result back to the client, it does not need to include this extra key material, and in this case only the orange bars corresponding to ciphertexts are of interest. Hence, these figures illustrate both the different transmission overhead for client-server and server-client communications, and the interest of using ω = 64 instead of ω = 32 for the client-server upload.

Smallest error is not always the best

As we described in the previous section, security and correctness directly depend on all the parameters: dimension, modulus and error size. Few relations exist and are not necessarily written black on white in the literature so we take the chance here to highlight them, before pushing the reasoning a bit further.

For a scheme to be correct, the error shall not be too big in front of the modulus, i.e. σ << q. We can grasp the idea that big errors will induce wrap-around q and mess things up. Yet for security, the error shall not be to small, σ > ω( √ n), otherwise the "masking" action we intend with error addition is not effective. So, we can say that

• Increasing q, increase correctness but reduce security.

• Increasing σ, decrease correctness but increase security.

Also, increasing n usually increase the difficult of the underlying problems so increase security, yet it magnifies the effect of the errors so can decrease the correctness. These three trends and their respective weights made us derive our Algorithm 5.9 to draw parameters, with a fixed σ = 2 √ n. We said we do not want to take it smaller, because of the hardness reduction (see [START_REF] Peikert | How (not) to instantiate ring-LWE[END_REF] for extensive details). Yet we might try to make it bigger with the hope to gain security without breaking correctness and so it may result in smaller parameters. We investigated this behaviour in more detail after we noticed it accidentally.

We took the case of FV for a depth 10 and 80 bits of security and derive parameters as before while fixing σ = x √ n with x varying from 2 to 200. Figure 5.4 displays the size of the resulting polynomials of degree n with coefficient size log q (again using Alg. 5.9. The ciphertext sizes and key sizes are multiple of n and log q.

Let us explain the phenomenon. We can see piecewise decreasing curves. For each of these pieces, increasing sigma makes the polynomials smaller. Indeed, a bigger error brings more security and so a smaller dimension is enough to reach the target security level. This is the behaviour we wished for. Yet, we observe a threshold effect of the size. The reason is that, if we continue to increase the error, the correctness is diminishing to the point when it no longer works. In such cases, we have to take a bigger modulus q (one more bit) to restore correctness, hence the jumps of the curve.

Taking one step back from the values, we see that the variation is limited, roughly 1% on this example. Yet every optimisation is interesting when considering deployment. However, in our exploration space of optimal parameters with three degree of freedom (n, σ, q), we had hoped that this third requirement (that of minimising the ciphertext) would have given us a global optimum, but it does not seem to be the case.

Implementation performance comparison

Now that we have done a thorough analysis of the parameters at hand within the different schemes, it would be of great interest to compare the actual performance of the scheme. It was a goal for us to continue in this direction. However comparing third party libraries in different languages or needing extensive tuning is always questionable.

In [START_REF] Lepoint | A comparison of the homomorphic encryption schemes FV and YASHE[END_REF], they chose to implement FV and YASHE' to compare them. This is a good approach because the skill of the programmer and the optimisation level would be very similar for all scheme. But it is quite time-consuming and there is always some more optimisation that can be done. Another approach (as in [START_REF] Herbert | Software implementation of 2-depth pairing-based homomorphic encryption scheme[END_REF]) involves using third party libraries with their default settings. This is also imperfect because some tuning could be done here and there to make things better. This would require to have good insights on all libraries.

To circumvent these limits, our idea was to take NFLlib [Qua], upon which there is a FV implementation [Cry] and write a similar implementation of SHIELD, with the aim to keep both implementations very similar. It would benefit from a highly optimised library for the core (costly) operations, while also keeping the scheme implementation comparable because they consists only in a "thin" layer over NFLlib. This work is partially done but not good enough to have been released yet [BM]. And so, the performance study is left for near future work.

Conclusion

We have detailed in this chapter our comparative study of homomorphic encryption schemes. This work was accepted for a special issue of IEEE Transactions on computers on Cryptographic Engineering in a Post-Quantum World [?]. Giving clues to an industrial implementer is the main outcome of our work.

Throughout this in-depth analysis, we were able to draw some general conclusions and pinpoint the most dimensioning questions to consider when going for homomorphic encryption use. Our study covered the most promising schemes as of 2016 and in the next chapter we will move on to the latest generation of schemes. This work does not set a final point on the matter. The latest proposals discussed below extensively change the criteria for choosing an encryption scheme. For an application we will always need to pick a scheme, and also maybe one of its implementations if several exist. In the future we may have heuristics for automatic selection of scheme and implementation.

As of now, we need them to mature more. The effort for a common API1 is a very good step forward.

Chapter 6 Construction of a new scheme

Becoming the chased mouse.

Additional

Circulant LWE and reduction to

Simpler error distribution in CLWE for

Building the

Known building

New building

Joining the building

As our last contribution, we endorsed a designer role. Thanks to the invitation of Léo Ducas, I joined the Centrum Wiskunde & Informatica (CWI) in Amsterdam between March and May 2017. During my stay, I worked with him and Max Fillinger on a new scheme that we called HE8, for "Homomorphic Evaluation over 8 bits". This new scheme is an improvement of FHEW and belongs to the new trend of bootstrapped schemes. It was accepted for Africacrypt 2018 [?]. The roadmap for this chapter is as follows: first we shall review the proposals of bootstrapped schemes, the fourth generation of homomorphic schemes. Then we describe the homomorphic gate, its elementary procedures and optimisations. And finally, we focus on the implementation aspects that I took care of during my time at CWI.

Introduction to the fourth generation

In the beginning of this dissertation we reviewed the young history of fully homomorphic encryption from Gentry's proposal in 2009 to the most mature BGV or FV as of this time.

Yet a new trend of homomorphic schemes arises, that of bootstrapped schemes. We could refer to them as the fourth generation but to the best of our knowledge, no one did so before. For a refresher on the different generations, consult Section 2. 4.1. This new kind of scheme has the interesting feature that the elementary operations supported by the scheme show no error growth. This trend emerged in 2014 with the work of Alperin-Sheriff and Peikert [START_REF] Alperin | Faster bootstrapping with polynomial error[END_REF]. Ducas and Micciancio released the scheme FHEW [START_REF] Ducas | FHEW: Bootstrapping homomorphic encryption in less than a second[END_REF] that can evaluate a NAND gate in time less than 1 second. More recently Chillotti et al. [START_REF] Chillotti | Faster fully homomorphic encryption: Bootstrapping in less than 0.1 seconds[END_REF] introduced TFHE which achieve even better performances: less than 0.1 second for common gates (NOT,AND, NAND, OR, XOR).

Our work builds upon the ideas of FHEW and introduces orthogonal improvements to that of [START_REF] Chillotti | Faster fully homomorphic encryption: Bootstrapping in less than 0.1 seconds[END_REF] with the aim of building an 8 bits generic gate. Concurrent work from the TFHE team [START_REF] Chillotti | Faster packed homomorphic operations and efficient circuit bootstrapping for TFHE[END_REF] brings even more improvements to TFHE. They released their work at the end of April 2017, exactly when we finished our implementation of HE8.

Additional preliminaries

Rings

Our FHE scheme uses circulant convolution rings (or, for short, circulant rings). Circulant rings of degree d will be denoted with indeterminate T : R d = Z[T ]/(T d -1). We fix two distinct odd primes p and q. When speaking specifically of rings R p , R q , and R pq we shall use indeterminates X, Y and Z, respectively. We write Rd for the cyclotomic ring Z[ T ]/Φ d ( T ) where Φ d ( T ) is the d-th cyclotomic polynomial.

We define the (normalised) trace function1 as follows: we let Tr * R d /Z : R d → Z, a � → a 0 . If d is clear from context, we simply write this function as Tr * . We let Tr * Rpq/Rp : R pq → R p be the linear function defined by This suggests a strategy to construct a variant of Ring-LWE over circulant rings that would be as secure as the cyclotomic Ring-LWE, simply by lifting all elements x ∈ Rd /Q Rd to x � (x, 0), yet this reverse CRT operation may not keep small elements small. Léo Ducas showed how to circumvent this obstacle in the published version of this work [START_REF] Bonnoron | Large FHE gates from tensored homomorphic accumulator[END_REF]. We detail the practical error sampling procedure in Section 6.2.4.

Tr * Rpq/Rp � Z k � = � X k/q if

LWE encryption

We recall the definition of the most basic LWE symmetric encryption scheme (see [START_REF] Blum | Cryptographic primitives based on hard learning problems[END_REF][START_REF] Regev | On lattices, learning with errors, random linear codes, and cryptography[END_REF][START_REF] Applebaum | Fast cryptographic primitives and circular-secure encryption based on hard learning problems[END_REF]). LWE symmetric encryption is parametrised by a dimension n, a plaintext modulus t ≥ 2, a ciphertext modulus Q = n O(1) and an error distribution χ. The message space of the scheme is Z t . (Typically, e ← χ satisfies the condition |e| < Q/2t, and t = 2 is used to encrypt message bits.) The (secret) key of the encryption scheme is a vector s ∈ Z n Q , which may be chosen uniformly at random, or as a random short vector

∈ LWE t|Q s (m) is err(c) = (b - �a, s� -�Q/t� m) mod Q, reduced modulo Q to the centered interval [-Q/2, Q/2).
Notice that the error err(a, b) depends not just on (a, b), but also on s, Q, t and m.

We use this LWE encryption to construct two encryption schemes, Circulant-LWE and Circulant-GSW (based on [START_REF] Gentry | Homomorphic encryption from learning with errors: Conceptually-simpler, asymptotically-faster, attributebased[END_REF]), which we need for our homomorphic accumulator (see Section 6.3). We do not specify any decryption procedures since we do not need any for the homomorphic accumulator.

Circulant-LWE encryption scheme

We let R, R, d, t and Q be as in Sections 6.2.1 and 6.2. 3. The Circulant-LWE scheme over R consists of the following algorithms:

• KeyGen: Output a uniformly random element s of R.

• Enc s (m) for m ∈ R/tR: Let (a, b) be a sample from the Circulant-LWE distribution over R with secret s and output (a, b � = b + �Q/t� • m).

We also define an n-dimensional variant of the scheme where the key is s ∈ R n , a is a random vector in R n and the product a•s is replaced by the inner product over R: �a, s� = � n i=1 a i •s i . Thanks to the reduction of Circulant-LWE, we have that the Circulant-LWE scheme is CPA-secure for messages of the form m = X k if the decisional R-LWE problem is hard.

We write

c ∈ R d LWE t|Q s (m; E) if c = (a, a t s + � Q t �
m + e) for some random error vector e that is E-subgaussian. We extend the notation to

C ∈ R d LWE t|Q s (m T ) for message m ∈ R k t that are vectors, meaning that the i-th column C i of C is in R d LWE t|Q s (m i ).
Furthermore, we write err(c) for the error term e in c. We may drop the information on the error size where it is not needed to make the notation easier.

Circulant-GSW encryption scheme

We let R, R, d, t and Q be as in Sections 6.2.1 and 6.2.3, and G as in Section 2.1. Furthermore, let t ≥ 2 be the plaintext modulus and B an integer ≥ 2, let K be the smallest integer such that B K ≥ Q.

The Circulant-GSW scheme is described by the following algorithms:

• KeyGen: Sample a uniformly random s from R.

• Enc s (m) for m ∈ R/tR: Generate a matrix A ∈ R 2K×2 where each row is a sample from the Circulant-LWE distribution with secret s. Output A + �Q/t� • mG.

We also define a n-dimensional variant of the scheme where A ∈ R (n+1)K×(n+1) and whose rows are samples from the n-dimensional Circulant-LWE and where G 1 is replaced by G n .

As before, we have that the Circulant-GSW scheme is CPA-secure if the decisional R-LWE problem is hard.

We write

C ∈ R d GSW t|Q s (m, E) if C = (a, as + e) + � Q t �
• mG, and the components of e are independent E-subgaussian variables. We write err(C) for the error vector e in C. We may drop the information on the error size where it is not needed, to make the notation easier.

Simpler error distribution in CLWE for practice

In practice, most FHE schemes do not follow precisely the Ring-LWE problem definition admitting reduction to worst-case problem [START_REF] Lyubashevsky | On ideal lattices and learning with errors over rings[END_REF]. For example, HElib [START_REF] Halevi | HElib: an implementation of homomorphic encryption[END_REF]HS15] uses Ring-LWE with spherical errors in the coefficient embedding, and very sparse ternary secrets, ignoring the co-different ideal R ∨ . The TFHE scheme [START_REF] Chillotti | Faster fully homomorphic encryption: Bootstrapping in less than 0.1 seconds[END_REF] also relies on Ring-LWE with ternary secrets, which is known to reduce to the regular Ring-LWE. Cutting such corners appears quite crucial to error growth management and therefore efficiency. We will follow this approach, and adjust the distributions as follows.

• First we sample secrets and error isotropically. Respecting the symmetries seems a must in the light of recent analysis [START_REF] Castryck | Provably weak instances of ring-LWE revisited[END_REF][START_REF] Peikert | How (not) to instantiate ring-LWE[END_REF].

• Then we choose to use ternary secrets s, which, as in previous schemes, leads to serious performance improvements due to smaller error growth. It has recently been shown that such choices make lattice attacks somewhat faster [Alb17], especially when s is very sparse, so we will account for this refined analysis when measuring the concrete security of our proposed parameters.

Sampling of a. We sample a uniformly in R d /(QR d ) under the constraint that a(1) = 0 mod Q. We achieve this by choosing all the coefficients a i at random for i ≥ 1, and setting

a 0 = - � i>0 a i mod Q.
Sampling of s. When d is prime, we sample a ternary s of density δ = 2/3 by choosing exactly �δd/2� coefficients set to 1 and �δd/2� coefficients set to -1. This implies that s(1) = 0, and �s� 2 = 2�δd/2�. Indeed, we find it preferable to fix its length to avoid sampling sparse keys that would be substantially weaker.

Sampling of e. We wish to sample errors e with variance σ in a way that ensures e(1) = 0.

We set:

e = σ 2 d/2 � i=0 T a i -T b i ,
where the a i 's and b i 's' are independent uniform exponents modulo d. One notes that this distribution is invariant by permutation over {1, T, . . . , T d-1 }: we have preserved the symmetries of the ring. Note that this procedure would get rather slow for large σ, yet we won't exceed σ ≤ 8 in our parameter choices. The above procedure would not be appropriate for composite degree d, as more care is required to construct a lift as done in section 6.2.2. Yet, while we will make use of circulant ring R d with composite degree d = pq, we will never directly construct ciphertexts over that ring. Indeed, the ciphertext in R pq will be publicly constructed by tensoring two ciphertexts from R p and R q , and are therefore no easier to decrypt than the original ciphertexts over R p and R q .

Building the gate

Before going into the detail of my contribution on the implementation of the scheme, we need to present briefly the multiple building blocks that compose the gate. Figure 6.1 presents an overview of the scheme and should be used as a guidance to understand this section. Some of the blocks (KeySwitch for example) do not appear anywhere because they belong to a superior detail level. In this section we present the building blocks and in the next, the optimisation that can be done on the structure or on some precise points.

Most of the operations presented below are meaningful both in the ring/circulant-setting or over the integers. We consider the RLWE problem over rings R

d = Z[X]/(X d -1) with d LWE t|pq s (m) c = (a, b) • mod p • mod q (a (p) , b (p) ) (a (q) , b (q) ) ExtExpInner ExtExpInner R p LWE t|Q sp � X b-�a,s� mod p � ModSwitch Q→Q⊗ R p GSW t|Q sp (X s i ) KS ψα(sp)→sp R q LWE t|Q sq � Y b-�a,s� mod q � ModSwitch Q→Q⊗ R q GSW t|Q sq (Y s i ) KS ψα(sq)→sq � ModSwitch Q⊗→Q � R pq LWE t|Q � spq � Z b-�a,s� mod pq � FunExpExtract f (� • �t:pq) LWE t|Q � s (f (m)) KS spq→s � ModSwitch Q � →pq � m = � γ i m i • • • ×γ 1 ×γ 2 ×γ k LWE t|Q � s (m 1 ) LWE t|Q � s (m 2 ) LWE t|Q � s (m k ) a (p) 1 a (p) 2 a (p) 3 . . . b (p) a (q) 1 a (q) 2 a (q) 3 . . . b (q) N f L c
On the left side, there are the k input bits m 1 , • • • , m k that get combined into m ∈ Z t . On the right side we have the two Homomorphic Accumulator ExtExpInner, which perform the linear part L c of the bootstrapped computation in a CRT fashion. After tensoring it is fed to the non-linear part of the computation N f : x � → f (�tx/q� mod t), i.e. FunExpExtract, where f is the function to be homomorphically evaluated. The computation is intrinsically done with the bootstrapping process, so the final output can directly be used as input. Grey boxes represent operations, white square boxes represent ciphertexts, and rounded white boxes represent key material. The linear step L c and the non-linear step N f discussed in the introduction are highlighted by dashed red circles. prime and over R = Z (i.e. simply the LWE problem). However, most of the results presented in this section also hold for cyclotomic rings. We assume that coefficients of ring elements in R/QR can be added and multiplied in constant time since, in our implementation, each coefficient fits into a machine word. Thus, adding two ring elements takes time O(d) and multiplying them takes time O(d log d) using FFT.

Below we omit the proofs of the algorithms because they are the work of Max Fillinger and involve some theory on sub-gaussian random variables which are outside the scope of our work. They can be found in the published version [BDF17].

Known building blocks

Let us first recall, within our formalism, known building blocks from the literature. The only novelty in this section concerns the FunExpExtract function: while this was already constructed in previous work, in our setup we will need to apply a trick from [START_REF] Gentry | Ring switching in BGV-style homomorphic encryption[END_REF] to improve its efficiency.

Linearity

Add : R d LWE t|Q s (m; E) × R d LWE t|Q s (m � ; E � ) → R d LWE t|Q s � m + m � ; √ E 2 + E �2 �
The Add operations are computed by simply adding the ciphertexts component-wise. Hence Add has a time complexity of O(nd). The error term in the result of Add holds when the error terms in the input ciphertexts are independent. Otherwise, it is E + E � .

x

∈ R d , Mult x : R d LWE t|Q s (m; E) → R d LWE t|Q s (xm; |x|E)
The Mult x operations work by scalar multiplication with x. The runtime is O(nd log d).

Modulus switching

In our scheme we need several times to change the ciphertext modulus.

ModSwitch Q→Q � : R d LWE t|Q s (m; E) → R d LWE t|Q � s � m; � (kE) 2 + 1 + � i |s i | 2 �
The basic idea of modulus switching is to multiply the ciphertext with Q � /Q, or rather �Q � /t� / �Q/t�. The runtime is O(d).

In practice, we only use modulus switching in the following two cases: when the dimension of the key is n = 1, and for short keys in Z n , i.e. n-dimensional keys where |s i | ≤ 1. In the first case, the error parameter simplifies to � (kE) 2 + 1 + |s| 2 , in the second case to � (kE) 2 + n + 1.

Key switching

In our scheme, we also change the key under which the ciphertexts are encrypted.

KeySwitch s→s � S : R d LWE t|Q s (m; E) → R d LWE t|Q s � � m; √ E 2 + σ 2 d 2 nK � . Algorithm 6.1 KeySwitch s→s � S (c): Transforms an R d LWE ciphertext under key s into a ciphertext under s � . Require: S = [S i ] i∈[n] where S i ∈ R d LWE Q|Q s � (s i • g T ). A ciphertext (a, b) ∈ R d LWE t|Q s (m) for some m ∈ R/tR. Ensure: A ciphertext c ∈ R d LWE t|Q s � (m) return (0 n � , b) -g -T (a) • S
As it is the case for FV and SHIELD (see previous chapter), the choice of the basis decomposition B for the gadget is important. It allows to trade off key size and running time against error growth. We use

S = � R d LWE 1,Q s � (B j s i ; σ) � i=1...n,j=0...K-1 , withK = �log B Q�
as key material. The key size decreases to O(nn � dK log Q), and the running time decreases to O(d log dnn � K), while the output error parameter also increases to

√ E 2 + σ 2 d 2 B 2 nK.

External Multiplication

Similarly as in FHEW and TFHE, we perform multiplication between R d LWE and R d GSW ciphertexts. The runtime of this operation is O(Kd log d).

ExtMult :

R d LWE t|Q s (T m ; E) × R d GSW t|Q s (T m � ; E � ) → R d LWE t|Q s � T m+m � ; √ E 2 + 2Kd 2 E �2 � Algorithm 6.2 ExtMult(c, C): Multiplies an R d LWE ciphertext and a R d GSW ciphertext into a R d LWE ciphertext. Require: A ciphertext c ∈ R d LWE t|Q s (T m ), and a ciphertext C ∈ R d GSW t|Q s (T m � ). Ensure: A ciphertext c � ∈ R d LWE t|Q s � T m+m � � . return G -1 � �Q/t� -1 • c � • C

Function extraction in the exponent

To construct our bootstrapped scheme, we need to somehow evaluate a function on the ciphertext and get the result back. However, this leads to an LWE ciphertext with quadratic dimension pq = Θ(n 2 ), that must be key-switched to a much smaller dimension Θ(n). Such a key-switch without any ring structure would require up to Θ(n 3 ) running time, and as much key material.

To circumvent this issue, we exploit the intermediate ring, following one of the tricks of [START_REF] Gentry | Ring switching in BGV-style homomorphic encryption[END_REF]. Namely, we choose a key in R p , which can also be viewed as an element of R pq . Exploiting the structure of R pq , switching to this key requires only Θ(pq) = Θ(n 2 ) operations. Then, one can trace a down to R p , and b down to Z, and obtain the desired result.

Require:

A

ciphertext c ∈ R pq LWE t|Q � spq (Z m ), A function F : Z pq → Z t , A key switching key S from s pq to s � ∈ R p ⊆ R pq , where s � = � p-1 i=0 (s pq ) i+1 X i . Ensure: A ciphertext c � ∈ LWE t|Q � s (F (m)). f ← � i∈Zpq F (i)Z -i mod pq ∈ R pq c ← KeySwitch spq→s � S (c) � ∈ R pq LWE t|Q � s � (Z m ) c ← Mult f (c) � ∈ R pq LWE t|Q � s � ( � i∈Zpq F (i)Z m-i mod pq ) (a, b) ← Tr * Rpq/Rp (c) (component-wise) � ∈ R p LWE t|Q � s � ( � i, st q|(m-i) F (i)X m-i mod pq ) a ← (a 0 , a p-1 , a p-2 , . . . , a 1 ) b ← Tr * Rp/Z (b) return (a, b) Algorithm 6.3 runs in time O(pq log(pq) log Q � ).
A careful look at the proof shows that we could reduce the error growth by performing the multiplication before the key-switch. However, doing the key-switch first allows to amortise the cost of gates with multiple outputs.

Indeed the algorithm consists in computing

c pq � → Tr * Rpq/Rp (f • G -T (c pq ) • S)
where the most expensive part of the computation G -T (c pq ) • S (i.e. the KeySwitch) can be re-used for several different f 's. Hence, at the cost of one KeySwitch we can extract multiple functions on the same input bits. This allows to construct more evolved gates with negligible extra costs.

New building blocks

In this part, we present the new elementary blocks that were introduced for this scheme.

Exponent Multiplication by Galois Conjugation

For α ∈ Z * d , we let ψ α be the automorphism of R d defined by T � → T α . We define a Galois Conjugation on ciphertexts

Galois : R d LWE t|Q s (T m ; E) → R d LWE t|Q ψα(s) (T αm ; E) .

CRT in the exponent by tensoring

A key trick from our scheme is that of combining the computation of two small (and fast) homomorphic accumulators into one result. This is the purpose of the ExpCRT operation.

ExpCRT : R p LWE t|Q ⊗ sp (X mp ; E p ) × R q LWE t|Q ⊗ sq (Y mq ; E q ) → R pq LWE t|Q ⊗ spq � Z m ; � E 2 p + E 2 q + t √ 2λE p E q �
where m = αm p +βm q is such that m p = m mod p and m q = m mod q and s pq = (-ψ α (s p )⊗ ψ β (s q ), ψ α (s p ) ⊗ 1, 1 ⊗ ψ β (s q )).

Note that we need t • �Q ⊗ /t� = 1 for the algorithm to be correct. This condition can be easily satisfied in our bootstrapping scheme because we perform a modulus switch before and after ExpCRT. Algorithm 6.4 runs in time Θ(pq).

Algorithm 6.4 ExpCRT

� c p , c q � Require: Ciphertexts c p ∈ R p LWE t|Q ⊗ sp (X mp ; E p ) and c q ∈ R q LWE t|Q ⊗ sq (Y mq ; E q ). Ensure: A ciphertext c ∈ R pq LWE t|Q ⊗ spq (Z m ) (a p , b p ) ← Galois α � c p � � ∈ R p LWE t|Q ⊗ ψα(sp) � X αmp ; E p � (a q , b q ) ← Galois β � c q � � ∈ R q LWE t|Q ⊗ ψ β (sq) � Y βmq ; E q ) a ← (a p ⊗ a q , a p ⊗ b q , b p ⊗ a q ) return (ta, tb p ⊗ b q )
External Multiply-and-Add in the exponent

We construct an (External) Multiply-and-Add operation in the exponent, for a public coefficient α ∈ Z * d . A similar speed-up was obtained in [CGGI16] using a different technique, namely a Mux operation. We are unfortunately unable to use it in our circulant setup, essentially because encryptions of 0 are not allowed: our IND-CPA-security guarantee only applies to encryptions of X m for some m ∈ Z d . Yet, our technique is more general, precisely we do not restrict the secret input vector to have binary coefficients.

ExtExpMultAdd : R d LWE t|Q s (T m � ; E) × R d GSW t|Q s (T m ; E � ) → R d LWE t|Q s � T αm+m � ; E �� � . Algorithm 6.5 ExtExpMultAdd α S α ,S β (c, C) Require: α ∈ Z * d , with inverse β = α -1 ∈ Z * d A ψ α (s) → s key switching key S α ∈ R d LWE Q|Q s � ψ α (s) • g T ; σ � A ψ β (s) → s key switching key S β ∈ R d LWE Q|Q s � ψ β (s) • g T ; σ � A ciphertext c ∈ R d LWE t|Q s (T m � ; E). A ciphertext C ∈ R d GSW t|Q s (T m ; E � ) Ensure: A ciphertext c � ∈ R d LWE t|Q s (T αm+m � ; � E 2 + d 2 K(4σ 2 + E �2 )). c 1 ← Galois β (c) � ∈ R d LWE t|Q ψ β (s) � T βm � � c 2 ← KeySwitch ψ β (s)→s S β (c 1 ) � ∈ R d LWE t|Q s � T βm � � c 3 ← ExtMult(C, c 2 ) � ∈ R d LWE t|Q s � T m+βm � � c 4 ← Galois α (c 3 ) � ∈ R d LWE t|Q ψα(s) � T αm+m � � c 5 ← KeySwitch ψα(s)→s S α (c 4 ) � ∈ R d LWE t|Q s � T αm+m � � return c 5 .

External Inner-product in the Exponent

By chaining, this allows us to evaluate inner products �x, y� over Z d in the exponent, given GSW encryptions R d GSW t|Q s (T x i ) and a public vector of coefficients y ∈ Z � d . This procedure allows evaluation of inner products in exponents with log d times less homomorphic additions in exponents than in FHEW, also less key material. Algorithm 6.6 runs in time Θ(lKd log d).

ExtExpInner y

[S α ]α : � � i=1 R d GSW t|Q s (T x i ; E � ) → R d LWE t|Q s � T �x,y� ; √ 2K� 2 d 2 σ 2 + 2K�d 2 E �2 � . Algorithm 6.6 ExtExpInner y [S α ]α ([C i ] i∈[l] ) Require: A public vector y ∈ Z � d A ψ α (s) → s key switching key S α ∈ R d LWE Q|Q s � ψ α (s) • g T � for each α ∈ Z * d A ciphertext C i ∈ R d GSW t|Q s (T x i ) for each i ∈ [�] Ensure: A ciphertext c ∈ R d LWE t|Q s � T �x,y� � . c ← (0, T 0 ) � ∈ R d LWE t|Q s (T 0 ; 0) for i from 1 to � where y i � = 0 do α = y i ; β = α -1 mod d c ← ExtExpMultAdd α S α ,S β (c, C i ) � ∈ R d LWE t|Q s � T � i j=1 x j y j � end for return c
In order to make things faster we also introduced (and implemented) two tricks.

Factoring Galois-KeySwitch sequences. We note that it is possible to factor some operations when chaining ExtExpMultAdd α and ExtExpMultAdd β , by applying Galois αβ -1 rather than Galois α followed by Galois β (together with the appropriate key-switches), as illustrated in Fig 6 .2. The implementation follows this approach. Furthermore, if y ∈ Z � d contains repeated values, it is possible to re-index the inner product to make equal values contiguous, and skip useless Galois 1 operations. Those tricks also decrease the final error E by constant factors. In practice we noticed that this re-indexing was more expansive than the gain. It may be possible to achieve a positive speed-up with this trick but we would need to look more closely at its implementation.

Pushing this trick to its limits, if � is large enough, one could re-index the inner product so that the αβ -1 all belong to a small subset Z * d (of size roughly d/� + 2, assuming the public vector y ∈ Z � d is uniformly random), allowing to decrease the size of the key material. In combination with the following optimisation, this should lead to reduce the overall key size by a significant factor. We did not attempt to implement this yet.

Decreasing LWE dimension. In our theoretical scheme, the homomorphic inner product in exponent operation is performed over vectors of length � = p + 1 where p is the dimension of the secret in the LWE scheme.

In practice, we remark that this dimension is quite larger than needed for security, given the amount of noise and the (small) modulus pq of those ciphertexts. We therefore

Galois y1/y2 RLWE t|Q ψ y 1 /y 2 (s) (T x1y1/y2 ) KeySwitch KS ψ y 1 /y 2 (s)→s RLWE t|Q s (T x1y1/y2 ) RLWE t|Q s (T 0 ) ExtMult RGSW t|Q s (T x2 ) RLWE t|Q s (T x1y1/y2+x2 ) Galois y2/y3 . . . . . . ExtMult RGSW t|Q s (T x � ) RLWE t|Q s (T �x,y�/y � ) Galois y � RLWE t|Q ψy � (s) (T �x,y� ) KeySwitch KS ψy � (s)→s ExtExpInner y 1 y 2 y � • • •
proceed with an extra LWE key-switch just after the combination of the LWE ciphertexts. In practice it allows to decrease the dimension by a factor between 2 and 3, which accelerates the ExtExpInner operations by the same factor. As a small added bonus, it also slightly decreases the error in the ciphertexts output by this function.

Joining the building blocks

In this section, we explain how the building blocks described above fit together to form the homomorphic evaluation and bootstrapping procedure EvalBootstrap. See Fig 6.1 for a schematic overview. We build an algorithm that, given ciphertexts c i ∈ LWE s (m i ; E in ), i ∈ {1, . . . , k} with s ∈ Z p Q � a short vector (i.e. s i ∈ {-1, 0, 1} for all i), a function f : Z t → Z t , and coefficients γ 1 , . . . ,

γ k ∈ Z t such that � i |γ i | ≤ t, produces c ∈ LWE s (f (m); E out ) where m = � k i=1 γ i m i .
We use the following parameters for the building blocks:

• n as the security parameter,

• p, q = Θ(n), Q = poly(n), K = �log Q� = O(log n), t = Θ(n) such that t ≤ √ pq/4,
• λ = Θ(n), such that λ ≤ q as the failure parameter; the decryption and homomorphic evaluation procedures should only fail with probability exponentially small in λ,

• σ as the error parameter used in the key material,

• Q � , Q ⊗ = O(Q/ √ nσ), with t • �Q ⊗ /t� = 1 mod Q ⊗ .
For m i ∈ {0, 1}, the algorithm can evaluate arbitrary k-bit gates if t ≥ 2 k , using γ i = 2 i-1 and an appropriately chosen f . We can compute a threshold gate if t > k by setting γ i = 1 for all i. Require: c i ∈ LWE t|Q � s (m; E in ), f : Z t → Z t , γ i ∈ Z t where γE in ≤ T for a certain T = Θ(Q/(n 2 √ σ)), and S is the required public key material consisting of:

• Bootstrapping keys BK � for α = q -1 mod p, and β = p -1 mod q, and s � = � p-1 i=0 (s pq ) i+1 X i Ensure:

c ∈ LWE t|Q � s � f �� k i=1 γ i m i � ; E out � where E out = O � |f |n 4.5 σ � c ← � k i=1 c i � ∈ LWE t|Q � s (m; γE � c ← ModSwitch Q � →pq (c) � ∈ LWE t|pq s (m;
� r 2 γ 2 E 2 + (p + 1) 2 ) where r = �pq/t� / �Q � /t� (a p , b p ) ← c mod p (a q , b q ) ← c mod q

c p ← X bp • ExtExpInner -ap [S p,α ]α � � BK (p) i � i � � ∈ R p LWE t|Q s � X b-�a,s� mod p ; O � n 2.5 σ �� c q ← Y bq • ExtExpInner -aq [S q,α ]α � � BK (q) i � i � � ∈ R q LWE t|Q s � Y b-�a,s� mod q ; O � n 2.5 σ �� c p ← ModSwitch Q→Q ⊗ (c p ) � ∈ R p LWE t|Q ⊗ s (p) � X b-�a,s� mod p ; O � n √ σ � � c q ← ModSwitch Q→Q ⊗ (c q ) � ∈ R q LWE t|Q ⊗ s (q)
� Y b-�a,s� mod q ; O � n √ σ � � c pq ← ExpCRT(c p , c q ) � ∈ R pq LWE t|Q ⊗ spq � Z b-�a,s� ; O � n 3.5 σ �� 4.5 σ �� return c

c pq ← ModSwitch Q ⊗ →Q � � c pq � � ∈ R pq LWE t|Q � spq � Z b-

Heuristic error propagation

Our theoretical analysis of the scheme used subgaussian analysis to provide bounds on error propagation that are already significantly better than worst-case bounds. Yet those bounds are asymptotic, without explicit constants, and for some operations may not be perfectly tight. As in previous work [START_REF] Ducas | FHEW: Bootstrapping homomorphic encryption in less than a second[END_REF][START_REF] Chillotti | Faster fully homomorphic encryption: Bootstrapping in less than 0.1 seconds[END_REF], when it comes to choosing practical parameters, we rely on a tighter but heuristic analysis of error propagation, essentially treating all random variables as independent gaussians. More precisely, considering that the critical random variable for correctness is obtained as the sum of many random variables, we only compute its variance as the sum of the variances of its terms, and treat this final result as gaussian in accordance with the central limit theorem (which is formally not applicable due to potential dependencies).

We refer to the original publication [?] for these better bounds that were derived by Léo and Max. We could successfully confirm all these heuristic equations by measuring the actual errors in our implementation.

Implementation

Now that we have presented the scheme in details, we can turn to the implementation challenges that constitute my contribution to this work. When I arrived at CWI in March 2017, the main aspects of the scheme were already there, based on Léo's and Max's works. We already had the overall Figure 6.1 in place. It remained to clear out some aspects such as proofs, practical error propagation, choice of parameters and implementation performance and tweaks. Working on this implementation kept me busy for my three months there. We shall present now the details of this contribution.

In the end, we developed a complete implementation of the scheme in C++11. Our objective was to make it efficient and easily usable by fellow cryptographers and users. The performance we got enabled us to homomorphically evaluate binary gates on six input bits in roughly 6.4 seconds on a regular laptop.

Data representation

As we saw above, there are several objects (in the board sense) to handle: different ciphertexts (LWE, R d LWE, R d GSW, . . . ), key materials (for encryption, key switching) and so on. To handle all this, we need to be able to have circulant ring elements in R d whose dimension d takes different values: p, q in the accumulator, pq in the function extraction or even 1 for the input/output of the gate. Also, all arithmetic operations are performed modulo different integers Q, Q � , Q ⊗ . . . We put in Figure 6.3 the full class diagram where each class has in subscript the parameter upon which it depends.

Low-level classes

At the bottom, we developed two classes: IntegerMod and CirculantRing to handle modular arithmetic and ring operations respectively. For performance reasons, we create the different integers and ring elements thanks to the template mechanism. As a reminder, the advantage of doing so is that the compiler will generate different binary code for all the different instances, so each type is optimised by the compiler. For example, modular arithmetic done with % operator modulo some power of 2 gets rewritten automatically with shifts by the compiler. The downside is a longer compilation time.

The IntegerMod class is then defined with one template attribute and contains one int64_t field to hold the value. for its coefficients (the ring does not know, and does not need to, the modulus) and the dimension of the ring. It has one dynamically allocated array of elements.

Fast multiplication with FFT

To perform the numerous FFTs of the scheme, we rely on a third party library FFTW [START_REF] Frigo | The design and implementation of FFTW3[END_REF]. It is a well-established, free and open-source, library with excellent performances so we provide a connector class FFT to handle the library calls. Working with FFTW implies that at the beginning of the programme some plans are computed (to be used to perform the FFT transforms later) with optimal performances on the computer used for execution. This wisdom is saved by our programme and has to be generated only once per computer. Each CirculantRing type (i.e. each template parameter set) has a static pointer to an FFT object to delegate the multiplication to it. We also add few static caches, that are allocated when the program starts and can be used for intermediary operations within CirculantRing.

It saves the many allocations/deallocations that would happen otherwise and badly impact the performances.

Since we are dealing with circulant ring elements, we may wish to run the FFT operation in the ring dimension exactly. We would benefit from the Wrapped Convolution property we discussed in the previous chapter. But we need our ring dimensions to be prime, which is the worst case for FFT efficiency. We ran some benchmarks and it turned out that it was much faster to use a bigger dimension (with small prime factors), and perform the polynomial reduction afterwards. Also, we do not meet the conditions to apply NTT (our moduli are not prime), so our choice was to stick with regular FFT computations. As such, each CirculantRing class has another template parameter: the FFT dimension.

More challenges arose with FFT computations since our biggest modulus is Q = 2 56 and the FFT works with double precision numbers (i.e. 53 bits mantissa). So we have to split the ring coefficients into two halves of 28 bits each (least and most significant parts) and apply the FFT transformation on each to prevent rounding errors and then perform the term by term multiplications correctly (à la Karatsuba). We perform this splitting trick only when needed, i.e. when the ring element at stake is not small. For example, in ExtMult products of ring elements are computed where one of them is the output of a Gadget decomposition. This operand does not need to be split before FFT forward transform because it is very small.

Gadget decomposition

For this aspect, we also created a dedicated class Gadget. The decomposition depends on the type to decompose, on the basis B used for the decomposition and on the size K of such decomposition. Again, we put these three parameters as template on the class. It consists only of two functions: one to generate the Gadget matrix used in R d GSW and the other to perform the actual g -T decomposition.

Predicates

The main objective of our scheme remains to evaluate a function on the input bits. So we provide the generic class to describe such a function f : Z t → Z t . Any user function can be described by derivation of the base class and the description can take any form (look-up table (LUT), linear expression, . . . ).

Encryptions

Using again the power of templates, we construct one generic RLWE class, taking two template parameters: the ring type of its elements and the size of the ciphertext. This size is that of the key which can be 1 in the case of a usual Ring-LWE (s is one ring element of size d) or many for LWE encryptions (s is n integers). Also, we have the case of Matrix-Ring-LWE as it happens in our scheme after the ExpCRT operation: the ciphertexts are then composed of 3+1 ring elements and the associated key s pq has also three components.

All this complexity is hidden to the user in the template parameters and the class RLWE has only two fields: an array a of ring elements (dynamically allocated with n elements) and another ring element b.

For R d GSW, the ciphertexts are a matrix of size nK × n of ring elements. So several template parameters are put in place for the RGSW class: the ring type, the size n, the decomposition basis B and size K. A static field links each type to the adequate gadget matrix computed by the Gadget interface.

Key switching keys

The last non-trivial component is the KSWKey class. Remember from the description of the building blocks above that a key switching key consists in several R d LWE encryptions of multiples of a key under another key. Hence, our KSWKey class takes several template parameters: the ring type like the others, the dimension of the source key n, that of the destination key n � and the decomposition basis B and size K. The object itself contains one field: a n × K array of R d LWE encryptions (of size n � ).

Further optimisations

Pre-computations. In order to minimise the evaluation time of the gate, a maximum of heavy computations is done in the setup phase. Consequently all key materials: bootstrapping keys, key switching keys, among others, are computed ahead of time and in FFT domain. Our CirculantRing class allows to transparently manipulate ring element in FFT or coefficient representation which greatly contributes to both performance and code readability.

Compiler options. We went into great lengths at optimising the algorithms and the different function calls and so on. We dived into the details with callgrind for precise function profiling to target our efforts. We also tweaked the optimisation flags of g++ to save up 5% more time than the usual -O2, which already saves 75% when compared to no flag at all.

The selected flags are: -Ofast, -march=native, -mtune=native, -fno-schedule-insns, -funroll-loops, -ffinite-math-only.

Open-source

Many efforts have also been made for general availability and usability. The whole code is documented with Doxygen and many unitary tests are provided. With under 4,000 lines of code, it remains accessible to whoever wants to tweak or improve it. The implementation is publicly available and open-source2 .

Tests. We provide extensive tests for every operations happening in the gate. They can be used for correctness checks, when playing with parameters for instance. We also provide statistical tests that allow to measure the output error for every steps in the scheme. They allowed us to confirm the heuristic error growth equations of Section 6.3.4.

Tweaking the parameters

Error growth and correctness. To choose the parameters, we simulated the error growth throughout the gate, using heuristic error propagation assumptions, described in Section 6. 3.4. We compared the predicted variance of each step to the experimental one, and found them to be quite close. From the final variance, and according to a central limit heuristic, we predict a failure probability of only 2 -74 for the parameter set below. In practice we have tested our scheme hundreds of time on different inputs, and never observed failure.

Security.

To estimate the concrete security of our parameter set, we use the lweestimator from Albrecht [START_REF] Martin R Albrecht | On the concrete hardness of learning with errors[END_REF]. All the LWE instances behind our LWE, R p LWE, R q LWE ciphertexts given as part of the evaluation key offers at least 100 bits of security. This is according to the estimator as of commit cc5f6e8, which includes the latest result of [START_REF] Albrecht | On dual lattice attacks against small-secret LWE and parameter choices in HElib and SEAL[END_REF] for small secrets. Therefore we feel safe to claim at least 80 bits of security.

Parameter sets. For our first implementation, we targeted a 6-bit gate. The parameters of the scheme are as follows:

• For 6 input bits, the plaintext modulus t = 2 6 .

• The ring dimensions p and q are 1439 and 1447, so pq = 2, 077, 892.

• Hence the FFT dimensions are d F F T 1 = 3072 = 3•2 10 for R p ,R q and d F F T 2 = 4, 194, 304 = 2 22 for R pq . Using 3072 gives us better results than 4096 despite it not being a power of two. This did not happen for d F F T 2 .

• The modulus in ExtExpInner and the LWE are Q, Q � = 2 56 .

• 2 × 790 MB of bootstrapping keys in ExtExpInner (all the R p GSW t|Q sp (X s i ) and R q GSW t|Q sq (Y s i ))

• 2 × 950 MB of key-switching keys in ExtExpInner (all the KS ψα(sp)→sp and KS ψα(sq)→sq )

• 2.9 GB for the key-switching key in FunExpExtract (KS spq→s � )

• 1.4 GB for the extra key-switching key on the LWE ciphertext prior to the ExtExpInner.

The input and output ciphertext size is 11.3 KB. The accumulators are 22.5 KB large each and after tensoring it is 63.5 MB.

Conclusion

In this last chapter, we detailed a new scheme, improving upon FHEW. We reported both the formal description and the implementation aspects we took care of. This contribution has been accepted to Africacrypt 2018 [?]. Another such improvement is the scheme TFHE [START_REF] Chillotti | Faster fully homomorphic encryption: Bootstrapping in less than 0.1 seconds[END_REF][START_REF] Chillotti | Faster packed homomorphic operations and efficient circuit bootstrapping for TFHE[END_REF]. In comparison to our work, TFHE offers better performances for generic gates. Though, our scheme is simpler: we have homogeneous inputs and outputs, so no need for bootstrapping. Our unique formalism for the function f is also simpler than the LUT and automata in TFHE.

With this work, we endorsed the last role of our journey, that of the implementer. Despite the hard competition there is around homomorphic encryption, our contribution has brought new concepts and techniques. As the one doing the actual implementation, our work spanned between the theoretical aims and the practical constraints. As with lattice reduction, this point is where we need works to close, or at least narrow, the gap between theory and practice.

The scheme presented here is in its infancy and could be extended and improved by further work, for example using RNS technique [START_REF] Bajard | A full RNS variant of FV like somewhat homomorphic encryption schemes[END_REF]. The fourth generation may however be the last, since now the noise is constant between gates. Still, there may be algorithmic improvements since the ideas of TFHE [START_REF] Chillotti | Faster packed homomorphic operations and efficient circuit bootstrapping for TFHE[END_REF] are very different from those in our scheme.

Chapter 7

Closing thoughts

Isn't it the goal of the traveller, never to be there?

We shall now wrap up the discussion about the last three years of work. Not that we intend to close the study of homomorphic encryption, but we hope we pushed forward both cryptography and cryptanalysis in this topic.

Retrospective

Started in April 2015, this journey led us first to endorse an attacker role. As a newcomer to the field, it has been a very stimulating task to try to break things down. Despite the limited reach of our new attack described in Chapter 3, the interaction with the community turned out to be very fruitful. Chapter 4 is a good illustration, about our contribution to algorithmic lattice reduction. A work that was mostly driven by the fplll days.

Next, within the context of the Lab-STICC, we were able to join forces, together with Vincent Migliore, to explore the practicality and the precise settings of homomorphic schemes, see Chapter 5 for all the details.

Finally, thanks to other encounters, we had the chance to join Léo Ducas and Max Fillinger at CWI for a few months. This allowed us to complete the circle and become a scheme designer and implementer, for real. Chapter 6 presents this line of work.

Our work in an evolving context

Following the trend around homomorphic encryption proved to be a real challenge. It required us to stay constantly tuned to the IACR ePrint Archive, with on average 2 or 3 highly relevant publications for us per month. With such a pace, the picture on homomorphic encryption has extensively changed since April 2015 and if we were to start our thesis today, our work would be conducted very differently. To keep only a few concurrent (and simultaneous) works, [LL15, Alb17] achieved similar and better results than what we report in Chapter 3. Then [START_REF] Costache | Which ring based somewhat homomorphic encryption scheme is best?[END_REF] offered similar outcomes as we did in Chapter 5. And lastly, [START_REF] Chillotti | Faster fully homomorphic encryption: Bootstrapping in less than 0.1 seconds[END_REF][START_REF] Chillotti | Faster packed homomorphic operations and efficient circuit bootstrapping for TFHE[END_REF] achieved better performances, in some cases, than we did at the same time (see Chapter 6).

Figure 1 -

 1 Figure 1 -Aperçu du schéma.

3. 1

 1 Review of the existing attacks

  Solving the system allows to recover the secret. With Gröbner bases it is possible to optimise the resolution [ACF + 15a].

(

  a m , b m ) = (a m , �a m , s� + e m mod q) We introduce the matrix A whose rows are the a i 's and denote the vectors b = (b 1 , b 2 , . . . , b m ) and e = (e 1 , e 2 , . . . , e m ). The equations above are summed up by the following: (A, b) = (A, As + e mod q)

Figure 3 .

 3 Figure 3.1 -Execution time in seconds in term of n for different η

Figure 3 . 2 -Figure 3 . 3 -

 3233 Figure 3.2 -Execution time in seconds in terms of n and q for different η

Figure 3 . 4 -Figure 3 . 5 -

 3435 Figure 3.4 -Success, Wrong and Failure cases

4. 1

 1 Review of reduction algorithms

Algorithm 4 . 1

 41 Perform a BKZ-β reduction on the input basis B 1: function BKZ(B: an LLL-reduced basis, β: the blocksize) 2:

  end function 7: function Tour(B: the current basis, β, the blocksize)8: for 1 ≤ j ≤ n do 9: k ← min(j + β, n) 10: v ←FindSVP(B, j, k)Let us know provide more details on the different steps.

Figure 4 . 2 -

 42 Figure 4.2 -Optimal choices for pre-processing block-sizes along BKZ-60 tours in dimension 100. From block position 0 to 100 it is the first tour, from 101 to 200 the second and so on.

  (a) GS slope evolution with and without a ramp-up phase (b) First basis vector norm evolution with and without a ramp-up phase

Figure 4 . 3 -Figure 4 . 4 -

 4344 Figure 4.3 -Basis quality improvement dynamic, with or without ramp-up

  SchemesAs we presented earlier in Section 2.4.1, the most practical SHE schemes in 2015 were: BGV[START_REF] Brakerski | leveled) fully homomorphic encryption without bootstrapping[END_REF], FV[START_REF] Fan | Somewhat practical fully homomorphic encryption[END_REF], YASHE[START_REF] Joppe W Bos | Improved Security for a Ring-Based Fully Homomorphic Encryption Scheme[END_REF] (in its optimised version dubbed YASHE'), SHIELD[START_REF] Khedr | SHIELD: scalable homomorphic implementation of encrypted data-classifiers[END_REF] (aka Ring-GSW) and F-NTRU[START_REF] Doröz | Flattening NTRU for evaluation key free homomorphic encryption[END_REF]. The three first of this list (BGV, FV and YASHE) belong to the second generation of HE schemes while SHIELD and F-NTRU belong to the third.YASHE and F-NTRU have been damaged by the sublattice attack from 2016 [KF17], so we had originally included them in the scope of our comparative study, but we dropped them later. The attack broke the security assumptions of both YASHE' and F-NTRU. YASHE is still secure but impractical and for F-NTRU the correctness and security constraints can no longer be satisfied.BGV differs significantly from FV and SHIELD, by its structure involving several moduli. So with hardware considerations in mind, we decided not to include it in our work. Accelerating hardware modular reduction with changing modulus seemed quite a challenge and not promising for performance. Nonetheless, BGV is a good candidate, especially when it comes to large plaintext moduli [GHS12b, CSVW16, JA16, CKKS17]. Several works also support the use of binary plaintext. Among other things, it enables more complex operators such as comparison. Hence our choice for FV and SHIELD.

5 . 3

 53 the usual encryption and decryption and Alg.5.4 presents the actual homomorphic elementary operations.It holds that � FV.PowersOf ω,q (a), FV.WordDecomp ω,q (b) � = [a × b] q .

  2 FV: Key generation functions 1: function FV.GenKeys(σ key , σ err )

Algorithm 5 . 3

 53 FV: Encryption/Decryption 1: function FV.Encrypt(m, p k , σ key , σ err ) 2: u ← D Rq,σ key 3: (e 1 , e 2 ) ← D 2 Rq,σerr 4:

4 3 :

 43 FV: Homomorphic operations 1: function FV.Add(c a , c b ) 2: c + ← (c 0 a + c 0 b , c 1 a + c 1 b ) return c + 4: end function 5: function FV.Mult(c a , c b ) 6:

5 3 :

 53 SHIELD: Utility functions1: function SHIELD.BitDecomp(A ∈ R N ×2 q ) for i = 0 to N -1 do 4:

q 9 :C 5 :

 95 end function Algorithm 5.7 SHIELD: Encryption/Decryption 1: function SHIELD.Encrypt(m, P k , σ err ) N×2 ← m • BDI(I N ) + r N×1 • P k + E N×2 return C N×2 6: end function 7: function SHIELD.Decrypt(C, S k ) 8: M ← C • S k 9: m ← �2/q × •M 0,0 � 10: return m 11: end function Algorithm 5.8 SHIELD: Homomorphic operations 1: function SHIELD.Add(C a , C b ) 2: C + = C a + C b 3: return C + 4: end function 5: function SHIELD.Mult(C a , C b ) 6:

  (a) Selection of parameters for FV. Binary key, σ err = 2 √ n.

( a )

 a Parameters for FV.

Figure 5 . 2 -

 52 Figure 5.2 -Data size required for FV and SHIELD in a scenario with 8 encryptions.

Figure 5 . 3 -

 53 Figure 5.3 -Histograms showing the respective size of ciphertexts and keys for FV with λ = 80. The lower (orange) part is the cumulative size of 8 ciphertexts and the upper part is the relinearisation key.

Figure 5 . 4 -

 54 Figure 5.4 -Ciphertexts and key sizes in term of σ

6. 1

 1 Introduction to the fourth generation. . . . . . . . . . . . . . .

  . The encryption of a message m ∈ Z t under key s ∈Z n Q is c = (a, b = �a, s� + e + �Q/t� m mod Q) ∈ Z n+1 Q where a ← Z n Q is chosen uniformly at random. A ciphertext (a, b) is decrypted by computing m � = �t(b -�a, s�)/Q� mod t ∈ Z t .We write c ∈ LWE t|Q s (m) to denote that c is an LWE-encryption of m, and c ∈ LWE t|Q s (m; E) if c is a random LWE-ciphertext such that c = (a, �a, s�+�Q/t� m+e) where e is a subgaussian random variable with parameter E. The error of c = (a, b)

Figure 6 . 1 -

 61 Figure 6.1 -Scheme overview.

Algorithm 6. 3

 3 FunExpExtract spq→s F,S : Turns an R pq LWE encryption of Z m into an LWE encryption of F (m).

  Given a R d LWE-ciphertext (a, as+�Q/t� T m +e), by applying ψ α component-wise, we obtain (ψ α (a), ψ α (a) • ψ α (s) + �Q/t� T αm + ψ α (e)). The running time is O(d), because for x ∈ R ψ α (x) is computed simply by permuting the coefficients of x. Even if the ciphertext is in FFT representation, the runtime remains O(d), as ψ α also acts on those representations by permutation.

Figure 6 .

 6 Figure 6.2 -Optimised ExtExpInner (External Inner Product in Exponent) overview

Algorithm 6 . 7

 67 EvalBootstrap f,γ 1 ,...,γ k S (c 1 , . . . , c k ): Homomorphically evaluates a function and produce a bootstrapped encryption of the result.

i

  ∈ R d LWE t|Q s (d) (s i mod d; σ) for i = 1, . . . , n and d = p, q • Key switching keys S d,α from ψ α (s) to s for d ∈ {p, q} and α ∈ Z * d • A key switching key S from s pq to s � where s pq= � -ψ α (s p ) ⊗ ψ β (s q ), ψ α (s p ) ⊗ 1, 1 ⊗ ψ β (s q )

  CirculantRing has two template parameters: the classCirculantRing Int,d,d F F T IntegerMod q FFT d F F T RLWE R,n Gadget R,B,K KSWKey R,B,K RGSW R,n,n � ,B,KR stands for a ring; d is the size of a ring; d F F T the FFT dimension for ring element multiplication; n and n � are numbers of ring elements; B and K are a decomposition basis and size.

Figure 6 . 3 -

 63 Figure 6.3 -Class diagram. The relation A → B reads "A needs B"

  The Chair of Naval Cyber Defence .. . . . . . . . . . . . . . . .

	Chapter 1
	Introduction
	Computer science is no more about computers than astronomy is about telescopes
	Edsger W. Dijkstra
	1.1

21 1.2 A walk through the history of cryptology . . . . . . . . . . . . . 22 1.2.1 What can crypto do for you? . . . . . . . . . . . . . . . . . . . . . 22 1.2.2 From paper-and-pencil to quantum... and post-quantum! . . . . . . 22 1.3 This thesis

  Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . 27 2.2 Some lattice theory . . . . . . . . . . . . . . . . . . . . . . . . . . 29 2.2.1 General definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 2.2.2 Gram-Schmidt Orthogonalisation (GSO). . . . . . . . . . . . . . . 30 2.2.3 Fundamental results . . . . . . . . . . . . . . . . . . . . . . . . . . 30 2.3 Lattice hard problems . . . . . . . . . . . . . . . . . . . . . . . . . Miscellaneous . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 2.4 Presentation of FHE . . . . . . . . . . . . . . . . . . . . . . . . . . Dimensioning constraints . . . . . . . . . . . . . . . . . . . . . . . 36 2.4.3 One example: the Fan-Vercauteren scheme (FV) . . . . . . . . . . 36

	been published in a special issue of IEEE Transations on computers on Cryptographic Engineering in a Post-Quantum World [?].
	• Finally, improving upon the state-of-the-art, we developed a new scheme, more effi-cient, together with an open-source implementation, see Chapter 6. It was accepted to Africacrypt 2018 [?]. Chapter 2
	Preliminaries
	Let your memory be your travel bag.
	2.1 30
	2.3.1 Shortest Vector Problem (SVP) and consorts . . . . . . . . . . . . 31
	2.3.2 Learning with errors (LWE) . . . . . . . . . . . . . . . . . . . . . . 32
	2.3.3 Learning with errors over rings (Ring-LWE) . . . . . . . . . . . . . 33
	2.3.4 34
	2.4.1 Homomorphic Encryption history (2008-2017) . . . . . . . . . . . . 34
	2.4.2
	This work has

Table 3 .

 3

1 -Successful breaks of SHIELD with diminished dimension scripting/developing in Python. This is a very comfortable setup to experiment on lattice reduction. Sage also includes Albrecht's lwe-generator

[Albc]

.

Table 5 .

 5 1 -Maximum log 2 q for a given dimension n, where λ is the security level. σ err = 2 √ n.

	n	2048	4096	8192	16384
	λ = 80 bits λ = 128 bits	89 bits 59 bits	174 bits 114 bits	348 bits 224 bits	695 bits 444 bits

Table 5 .

 5 3 -Parameters for SHIELD, where λ is the security level and L the multiplicative degree. Optimized circuit. Binary message (No batching). Binary key, σ err = 2 √ n.

	L	log 2 q	λ = 80 bits	n	log 2 q	λ = 128 bits	n
	1 5 10 15 20	36 38 40 40 41		752 803 849 854 869	38 40 41 42 43		1247 1323 1363 1396 1429

Table 5 .

 5 4 -Parameters for FV and SHIELD in the case of the NWC NTT, where λ is the security level and L the multiplicative depth. Binary key, σ err = 2 √ n. Reminder: no batching with the NWC NTT.

Table 5 .

 5 6 -Parameters of FV for 80 bits of security when batching is enabled, where L is the multiplicative depth, batching the number of packed operations, m the rank of the cyclotomic polynomial and weight of the number of non-zero monomials in the associated cyclotomic polynomial. Binary key, σ err = 2√ n

	Range of n L	batching	weight	m	Actual n
			2	7	3375
		1	6 12	9 33	3087 2835
	[1024, 2048]		24 2	59 7	2925 3645
		2	6 18	17 49	3159 2997
			20	57	4125
			2	7	5625
		3	6 18	9 25	5103 4617
			30	49	3875
			2	7	6075
	[2048, 4096]	4	6 12	23 33	4459 7875
			20	57	7425
			2	17	6591
		5	12 24	33 59	8505 7605
			40	65	5125
			2	7	9375
		6	10 12	17 33	6875 11025
	[4096, 8192]		20 2	57 7	9075 10125
		7	6 18	9 25	9261 9747
			20	57	12375

  It is well known that the naive decisional version of Ring-LWE is insecure over circulant rings, simply by exploiting the CRT decomposition. Say that d is prime, and note thatR d /QR d � Rd /Q Rd × Z/QZ if Q is co-prime to d,so one may mount an attack on the Z/QZ part (projecting to this part corresponds to evaluating the polynomial at 1, and therefore maintain smallness of the error). However, this does not mean that such rings are inherently insecure: the NTRU cryptosystems [HPS98, HHGP + 03] use circulant rings, choosing the secret key and errors that evaluate to a fixed known value (say 0) at 1.

	6.2.2 Circulant LWE and reduction to Ring-LWE
		q|k
	0	otherwise
	It is easy to see that: Tr * R d /Z and Tr * Rpq/Rp are linear, and: Tr * Rp/Z • Tr * Rpq/Rp = Tr * Rpq/Z .

  In our scheme, this is achieved with FunExpExtract. It takes what comes out of the homomorphic accumulator. Z pq → Z t where |F | = � i∈Zpq |F (i)| and s ∈ Z p . Let us first consider the function F 0 that maps 0 � → 1 and k � → 0 for k � = 0. If we can extract this function, we can extract any function by first multiplying the ciphertext with an appropriate polynomial. This extraction is easily provided by the trace function Tr * = Tr * Rpq/Z . Indeed, if (a, b) ∈ R pq LWE s (m), then (a, Tr * (b)) ∈ LWE s (m 0 ), where a, s ∈ Z pq are the vectors of coefficients of a and s.

	FunExpExtract	spq→s F,S	: R pq LWE t|Q � spq (Z m ; E) → LWE t|Q � s � F (m); |F |	�	E 2 + 3σ 2 p 2 q 2 K	�
	for some function F :

•

  Determination and exploration of practical parameters for the latest somewhat homomorphic encryption schemes, with Vincent Migliore and Caroline Fontaine, IEEE Transactions on computers, special issue on Engineering in a Post-Quantum World, 2018 [?] • Large FHE gates from Tensored Homomorphic Accumulator, with Léo Ducas and Max Fillinger, Africacrypt 2018 [?] Source code • Maintainer of HE8, public repository, https://github.com/gbonnoron/Borogrove • Contributions to fplll, public repository: https://github.com/fplll/fplll • Contributions to SHIELD-NFLlib, private repository: https://github.com/ gbonnoron/SHIELD-NFLlib

https://www.ecole-navale.fr/Chaire-de-cyberdefense-des.html

in French: https://www.ecole-navale.fr/Chaire-de-cyberdefense-des.html

https://github.com/fplll/fplll/pull/191

https://github.com/fplll/fpylll/blob/master/src/fpylll/algorithms/simple_bkz.py

https://github.com/bristolcrypto/HEAT

This is simply a special case of the usual definition of the trace function, but we do not need the general definition here.

https://github.com/gbonnoron/Borogrove

Chapter 5

Comparing and using schemes correctly

Where we demonstrate that the best security is not the highest. • Errors and secrets are sampled according to Section 6.2. 4. Secrets are ternary, one third of the coefficients are set to -1, another to 1 and the rest to 0. Errors have variance 4.

• For ExpCRT we want a small inverse to �Q ⊗ /t� mod Q ⊗ . Hence we choose Q ⊗ = (2 19t + 1) 2 which gives us

• Finally, for the gadget decomposition we use B = 2 8 and K = 7 for ExtExpInner and FunExpExtract and their key material.

We also have extra parameters related to the optimisation ExtExpInner. Namely, we apply an extra KeySwitch over the LWE ciphertext to decrease its length l of the innerproduct from l = p = 1439 down to l = 600. This key-switch happens with modulus Q = 2 56 , error standard deviation 2 33 , and gadget parameters B = 2 6 , K = 10.

Performances

Time

We run our test on a punchy laptop: Core i7-6500U (2.50 GHz, 4MB L2 cache), 16 GB RAM with a GNU/Linux Fedora 26 installed on a SSD. The computation is single-threaded and we got the following timings:

• FFTW wisdom computation (only once per computer): 68 minutes

• Key pre-processing (once per user key pair): 38 seconds • 6-bit input, 1-bit output gate evaluation: 6.4

seconds

The gate time breaks down into:

• 0.60 s per ExtExpInner (the two could be run in parallel);

• 4.0 s for the KeySwitch in FunExpExtract;

• and only 0.55 s for the output bit related operations.

Consequently, computing another function (1 more output bit) on the same 6 input bits would add only 0.55 s, and so on. For 6-to-6 bit gate it yields just above 10 seconds.

Memory

On the memory front, we need 9.2 GB of RAM to store all key materials and for the computation. The usage breaks down as follows

• 52 MB of secret keys (s, s p , s q , s pq ) CHAPTER 7. CLOSING THOUGHTS

Perspectives

We are definitely not at the end of our journey. Below we share our thoughts for works that could help push further the research efforts we joined during the thesis.

On targeted attacks. As most recently illustrated by the work of Albrecht [START_REF] Albrecht | On dual lattice attacks against small-secret LWE and parameter choices in HElib and SEAL[END_REF] against the settings of HElib [Hal] and SEAL [START_REF] Laine | Simple Encrypted Arithmetic Library -SEAL v2.3[END_REF], we can still expect better attacks for such or such case. As we saw with YASHE' and F-NTRU, we shall not advocate the use of schemes that do not stand on a hard ground. Hence, when we see that today most of the homomorphic encryption libraries choose not to comply with the hardness reduction conditions, we can expect some troubles in the future.

To this end, we encourage cryptanalytic efforts or more efficient security reductions to make things clearer for everyone.

On lattice reduction. The last fplll days of December 2017 put a focus on implementing sieve algorithms for SVP/CVP. Indeed, we can expect that, in a near future, enumeration will be beaten by sieving for the instances of interest. Thus, lattice reduction will continue to improve, whether with generic libraries like fplll or with more confidential special-purpose implementation. Many heuristics remain to be experimented with and many parameters to tune. Thanks to the speed of fplll core and fpylll flexibility, we think playing within this framework should be fruitful.

On scheme improvements. Homomorphic Encryption reaches the age of maturity and we start to see industrialised framework [CL] that aims further than proof-of-concept implementations. We can expect many efficiency improvements and we think there is also space for algorithmic leaps. Also, we think there will always be several lines of candidates, each with its distinguishing features. The choice for the best will depend on the context, yet we will have generically good schemes. Pre-prints Abstract : 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).

Appendices Disseminations

List of Algorithms

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.