Chiffrement homomorphe

		Mémoire de fin d'études En vue de l'obtention du Diplôme de Master2 Recherche Spécialité : Sécurité Informatique
		CHIFFREMENT HOMOMORPHE
		Présenté et soutenu par: MOUYOUME Dieudonné Maticule :13Y369 Licence en Informatique Devant le jury: Examinateur: Pésident : Directeurs:
		Pr. NDOUNDAM Réné Université de Yaoundé I	Pr. BOUETOU BOUETOU Thomas Université de Yaoundé I Année académique :2022/2023		Dr. HERVE TALE KALACHI Université de Yaoundé I Pr. PASCAL LAFOURCADE Université de Clermont Auvergne
		Mémoire de fin d'études En vue de l'obtention du Diplôme de Master2 Recherche Spécialité : Sécurité Informatique
		CHIFFREMENT HOMOMORPHE
		Présenté et soutenu par: MOUYOUME Dieudonné Maticule :13Y369 Licencié en Informatique Sous l'encadrement de : Examinateur: Pésident : Directeurs:
		Pr. NDOUNDAM Réné Université de Yaoundé I	Pr. BOUETOU BOUETOU Thomas Dr. HERVE TALE KALACHI Université de Yaoundé I Université de Yaoundé I Pr. PASCAL LAFOURCADE Université de Clermont Auvergne Année académique :2022/2023

Mémoire de Master 2 Recherche i MOUYOUME DIEUDONNE(c) UYI

Dédicace

Je dédie ce mémoire à ma très chère mère

Mémoire de Master 2 Recherche ii MOUYOUME DIEUDONNE(c) UYI

REMERCIEMENTS

Au terme de ce travail, j'exprime toute ma gratitude au Seigneur tout-puissant de m'avoir donné la force et les moyens de le réaliser.

Je remercie:

· Le Coordonnateur de l'école doctorale, Pr. Raoul AYISSI

· Le Chef de laboratoire UMMISCO, Pr. Réné NDOUNDAM,

· Le Chef du département d'Informatique Dr. HAMINOU Halidou pour la mise en oeuvre des conditions adéquates pour la réussite de notre soutenance.

Je remercie particulièrement mes encadrants:

· Le Pr. Pascal LAFOURCADE,

· Le Dr. Hervé TALE KALACHI

qui ont accepté m'encadrer.

Je remercie aussi tous les étudiants de Master 2 recherche en sécurité informatique de la promotion 2022-2023 du Département d'Informatique de l'Université de Yaoundé I, avec qui nous avons partagé beaucoup d'expériences.

En fin, je remercie mes amis Dr. MBA Mathieu Lionel de l'Université de la Sorbonne, MESSI Guy Célestin, Doctorant en Géographie à l'Université de Yaoundé I, BIATAT Cédric Doctorant en Sciences de l'ingénieur à l'Université de Douala et JOB GOUET Frank Maurice, Enseignant d'Informatique Industrielle pour leurs soutiens et leurs encouragements.

RESUME

Le chiffrement entièrement homomorphe (FHE) permet d'effectuer des calculs sur des données chiffrées, préservant ainsi la confidentialité des informations tout au long du processus. Ce mémoire compare les coûts en termes de temps de calculs des bibliothèques homomorphiques Miscrosoft SEAL, openFHE et PALISADE dans le contexte de la multiplication matricielle en utilisant les cryp-tosystèmes Brakerski-Fan-Vercauteren (BFV) et Brakerski-Gentry-Vaikuntanathan(BGV). La multiplication matricielle étant une opération fondamentale dans de nombreux domaines, tels que l'appren-tissage machine et le traitement des données. Nous mettons sur pieds un environnement expérimental en écrivant des programmes en langage C++ intégrés dans ces bibliothèques pour faire la multiplication homomorphe et comparer les temps de chiffrement, de déchiffrement et temps de multiplication homomorphe après 100 itérations, afin de comparer les performances de ces bibliothèques. Les résultats obtenus nous montrent que OpenFHE est plus performante que PALISADE et Microsodt SEAL dans le cas du cryptosystème BFV alors que Microsoft SEAL est plus performante que PALISADE et OpenFHE dans le cas du cryptosystème BGV.

Mémoire de Master 2 Recherche iii MOUYOUME DIEUDONNE(c) UYI

Mots clés : Bibliothèques homomorphiques, FHE, BFV, BGV.

ABSTRACT

Fully homomorphic encryption (FHE) allows computations to be performed on encrypted data, preserving the confidentiality of the information throughout the process. This paper compares the computation time costs of the Miscrosoft SEAL, openFHE and PALISADE homomorphic libraries in the context of matrix multiplication using the Brakerski-Fan-Vercauteren (BFV) and Brakerski-Gentry-Vaikuntanathan (BGV) cryptosystems. Matrix multiplication is a fundamental operation in many fields, such as machine learning and data processing. We are setting up an experimental environment by writing programs in the C++ language integrated with these libraries to perform ho-momorphic multiplication and compare the encryption, decryption and homomorphic multiplication times after 100 iterations, in order to compare the performance of these libraries. The results show that OpenFHE outperforms PALISADE and Microsodt SEAL for the BFV cryptosystem, while Microsoft SEAL outperforms PALISADE and OpenFHE for the BGV cryptosystem.

Mémoire de Master 2 Recherche iv MOUYOUME DIEUDONNE(c) UYI

Keywords : Homomorphic libraries, FHE, BFV, BGV.

Mémoire de Master 2 Recherche v MOUYOUME DIEUDONNE(c) UYI

Table des matières

Dédicace i

Remerciements ii

Résumé iii

Abstract iv

Table des figures viii

Liste des tableaux ix

Abréviations x

Introduction générale 1

1 GENERALITES 5

1.1 Notions mathématiques 5

1.1.1 Structures algébriques 5

1.1.2 Problèmes difficiles sur les entiers 7

1.1.3 Distributions de probabilités 9

1.1.4 Problèmes sur les réseaux euclidiens 10

2 ETAT DE L'ART DU CHIFFREMENT HOMOMORPHE 17

2.1 Chiffrement homomorphe 17

2.1.1 Algorithmes d'un système de chiffrement homomorphe 18

2.1.2 Types de chiffrements homomorphes 18

2.2 Générations du chiffrement homomorphe 20

2.2.1 Pré-FHE 20

2.2.2 FHE de première génération 24

2.2.3 FHE de deuxième génération 24

2.2.4 FHE de quatrième génération 25

2.2.5 Cryptosystèmes basés sur le problème Ring-LWE 25

2.2.6 Quelques applications du FHE 29

Mémoire de Master 2 Recherche vi MOUYOUME DIEUDONNE(c) UYI

TABLE DES MATIÈRES

vi			3
2.2.7 Avantages du FHE 2.2.8 Limites des techniques actuelles de chiffrement homomorphe SYSTEMES DE CALCULS HOMOMORPHES 3.1 Bibliothèques logicielles 3.1.1 Conception et organisation des bibliothèques 3.1.2 Principes 3.2 Bibliothèques FHE	31 31 33 33 33 34 34
	3.2.1 HElib	35
	3.2.2 HEAAN	35
	3.2.3 Lattigo	36
	3.2.4 ?oë(Lol)	36
	3.2.5 FHEW	36
	3.2.6 NFLlib	37
	3.2.7 cuHE	37
	3.2.8 TFHE	38
	3.2.9 pyFHE	39
	3.2.10 TenSEAL	39
	3.2.11 Concrete	39
	3.2.12 Microsoft SEAL	40
	3.2.13 OpenFHE	40
	3.2.14 PALISADE	41	4
ETUDE DE L'EXISTANT	43		5
IMPLEMENTATION ET RÉSULTATS	52
5.1	Choix des cryptosystèmes FHE	52
	5.1.1 Classes de calculs HFE	52
	5.1.2 Choix des paramètres de chiffrement	54
5.2	Choix des bibliothèques FHE	55
	5.2.1 Environnement	56
	5.2.2 Langage de programmation et éditeurs utilisés	56
5.3	Installation des bibliotèques FHE	56
	5.3.1 Installation de SEAL Version 4.1.1	57
	5.3.2 Installation de OpenFHE	57
	5.3.3 Installation de PALISADE	58
5.4	Multiplication Matricielle	58
	5.4.1 Algorithme de multiplication matricielle na^·ive	58
	5.4.2 Algorithme de multiplication homomorphe matricielle	59
5.5	Tests	60

TABLE DES MATIÈRES vii

Mémoire de Master 2 Recherche vii MOUYOUME DIEUDONNE(c) UYI

5.5.1 Le cas de SEAL 60

5.5.2 Le cas de OpenFHE 60

5.5.3 Le cas de PALISADE 60

5.6 Exécution des programmes 61

5.6.1 Cas de SEAL 61

5.6.2 Cas de OpenFHE 61

5.6.3 Cas de PALISADE 62

5.7 Résultats obtenus et discussions 62

5.7.1 Utilisation du cryptosystème BFV 63

5.7.2 Utilisation du cryptosystème BGV 64

Conclusion et perspectives 65

Bibliographie 67

Mémoire de Master 2 Recherche viii MOUYOUME DIEUDONNE(c) UYI

Table des figures

1.1 La distribution normale réduite avec les aires centrales autour de 1 et 2 écarts types

mises en évidence 10

1.2 Exemple d'un réseau euclidien 11

1.3 Un réséau engenré par la mauvaise base (b1, b2)[42] 12

1.4 Même réséau engenré par bonne base (u1, u2)[42] 12

1.5 Le CVP 13

1.6 Le SVP 14

2.1 Simple scénario fondé sur le chiffrement homomorphe dans le could 18

5.1 Sélection des paramètres 55

5.2 Exécution du programme avec BGV 61

5.3 Exécution du programme avec BFV 61

5.4 Exécution du programme avec BGV 61

5.5 Exécution du programme avec BFV 61

5.6 Exécution du programme avec BGV 62

5.7 Exécution du programme avec BFV 62

5.8 Temps du chiffrement 63

5.9 Temps de la multiplication 63

5.10 Temps du déchiffrement 63

5.11 Temps du chiffrement+ déchiffrement+multiplication 63

5.12 Temps du chiffrement 64

5.13 Temps de la multiplication 64

5.14 Temps du déchiffrement 64

5.15 Temps du chiffrement+ déchiffrement+multiplication 64

Mémoire de Master 2 Recherche ix MOUYOUME DIEUDONNE(c) UYI

Liste des tableaux

2.1	Types de chiffrement homomorphe		20	2.2
Comparaison des capacités homomorphes	23		2.3
Tableau récapitulatif des cryptosystèmes FHE	25		3.1
Plateformes d'utilisation de SEAL	40		3.2
Bibliothèques FHE	42		4.1
Performances relatives par cryptosystème	50		4.2
Syntèse sur l'étude de l'existant des bibliothèques FHE	51		5.1
Paramètres de chiffrement	55

Mémoire de Master 2 Recherche x MOUYOUME DIEUDONNE(c) UYI

ABREVIATIONS

SEAL Simple Encrypted Arithmetic Library

BGV Brakerski-Gentry-Vaikuntanathan

BFV Brakerski/Fan-Vercauteren

OpenFHE Open-Source. Fully Homomorphic Encryption Library

DM Ducas-Micciancio

CGGI Chillotti-Gama-Georgieva-Izabachene

NTT Number Theoretic Transform

FHE Fully Homomorphic Encryption

RLWE Ring Learning With Error

CKKS Cheon-Kim-Kim-Song

RNS Residus Number System

HEAAN Homomorphic Encryption for Arithmetic of Approximate Numbers

HElib Homomorphic Encryption library

cuHE CUDA Homomorphic Encryption Library

MIT Massachusetts Institute of Technology

IBM International Business Machines

BGN Boneh-Goh-Nissim

RSA Rivest, Shamir et Adleman

LFHE Leveled Fully Homomorphic Encryption

BLLN Bos, Lauter, Loftus et Naehrig

SVP Shortest Vector Problem

CVP Closest Vector Problem

SIMD Single Instruction/Multiple Data

Mémoire de Master 2 Recherche xi MOUYOUME DIEUDONNE(c) UYI

NOTATIONS

7L Ensemble des nombres entiers

R Ensemble des nombres entiers

7L/n7L Corps, avec n premier

1x1 Valeur absolue de x

Lxi Partie entière de x

1x1 Entier immédiatement supérieur à x

R_q = 7L_q[x]/(xⁿ + 1) Anneau de polynômes

11.11 Norme euclidienne

£ Réseau euclidien

B = (b1,. . . ,bd) Base du réseau euclidien de dimension d

d Dimension du réseau £

K[X] Anneau de polynômes à coefficients dans K

Mémoire de Master 2 Recherche xii MOUYOUME DIEUDONNE(c) UYI

GLOSSAIRE

Cryptologie Science des messages secrets, elle est composée en deux disciplines : la Cryp-

tographie et la cryptanalyse.

Cryptographie Art de transformer un message clair en un message inintelligible par celui qui
ne possède pas les clés de chiffrement.

Cryptanalyse Art d'analyser un message chiffré afin de le décrypter.

Chiffrement Procédé qui consiste à transformer une donnée (généralement un message

texte) afin de la rendre incompréhensible à toute personne qui ne connait pas la clé.

Déchiffrement Procédé qui consiste à retrouver le texte clair à partir du texte chiffré.
Cryptogramme Texte chiffré ou message chiffré.

Clé Séquence sécrète en bits qui permettent de chiffrer ou de déchiffrer un mes-
sage donné.

Bibliothèque ho- Ensemble de fonctions homomorphes utilitaires, regroupées et mises à dispo-

momorphique sition afin de pouvoir être utilisées sans avoir à les réécrire.

Mémoire de Master 2 Recherche 1 MOUYOUME DIEUDONNE(c) UYI

INTRODUCTION GENERALE

Contexte

La cryptographie est un terme qui a vu le jour au XVII^e siècle. Il se compose à l'aide de deux mots grec kruptos, « caché », et graphein, « écrire ». C'est l'art d'écrire en langage codé, secret, chiffré. En général, la cryptographie est une technique d'écriture où un message chiffré est écrit à l'aide de codes secrets ou de clés de chiffrement. La cryptographie est principalement utilisée pour protéger un message considéré comme confidentiel. Cette utilisation a aujourd'hui un intérêt d'autant plus grand que les communications en ligne circulent dans des infrastructures dont on ne peut garantir la fiabilité et la confidentialité. Désormais, la cryptographie sert non seulement à préserver la confidentialité des données, mais aussi à garantir leur intégrité et leur authenticité. Il existe deux principaux types de chiffrement : le chiffrement symétrique et le chiffrement asymétrique. Le chiffrement symétrique utilise une seule clé pour chiffrer et déchiffrer les données. Cette clé doit être partagée entre les deux parties qui souhaitent communiquer de manière sécurisée. Les algorithmes de chiffrement symétrique sont généralement plus rapides que les algorithmes de chiffrement asymétrique, mais il se pose un problème de partage de la clé sécrète, car il faut que les deux parties trouvent un moyen sécurisé pour se partager la clé. L'essor du chiffrement asymétrique remonte à 1976 avec la publication fondatrice de Diffie et Hellman, « New directions in cryptography » [49]. Ce mécanisme révolutionnaire introduit un paradigme à double clé : une clé publique librement partageable et une clé privée rigoureusement confidentielle. Parmi ses implémentations pratiques, le système RSA [45] s'impose dès 1978 comme référence incontournable, marquant une avancée majeure dans la sécurisation des échanges numériques.

Cependant, les schémas cryptographiques classiques (AES, RSA) révèlent des limitations criantes dans l'ère du cloud computing. Leur exigence systématique de déchiffrement préalable avant tout traitement expose les données à des risques critiques. Cette contrainte devient particulièrement problématique face à la tendance croissante des utilisateurs à externaliser des calculs complexes vers des infrastructures cloud. Bien que le chiffrement des données avant transfert semble offrir une protection théorique, il crée un dilemme opérationnel : les fournisseurs de services doivent nécessairement accéder aux données en clair pour exécuter les traitements, annihilant ainsi le bénéfice initial du chiffrement.

Cette vulnérabilité intrinsèque ouvre la porte à des exploitations malveillantes potentielles, no-

LISTE DES TABLEAUX 2

Mémoire de Master 2 Recherche 2 MOUYOUME DIEUDONNE(c) UYI

tamment par des acteurs cloud peu scrupuleux. Même avec des protocoles d'accès stricts, la phase de déchiffrement constitue une fenêtre critique où les données sensibles (dossiers médicaux, secrets industriels, informations financières) deviennent accessibles en clair. Un paradoxe se dessine donc: l'outil même censé protéger les données (le chiffrement) devient un obstacle à leur utilisation sécurisée dans les architectures cloud modernes. Mais il se pose alors la question de savoir si le déchiffrement du résultat des calculs sur les données chiffrées sera le même que le résultat des calculs sur les données en clair. Si l'on suppose qu'on veut effectuer une opération * entre deux données en clair m1 et m2, étant données une fonction de chiffrement _EncKp et une fonction de déchiffrement DecK_s, on aimerait avoir DecK_s(EncKp(m1) * EncK_p(m2)) = m1 * m2. L'on peut remarquer qu'il suffit d'avoir EncK_p(m1) * EncK_p(m2) = EncK_p(m1 * m2). Il faut donc de choisir un système de chiffrement qui vérifie de telles propriétés. Un tel système est appelé système de chiffrement homomorphe. Le système RSA ne vérifie malheureusement pas cette propriété pour toutes les opérations à savoir l'addition et la multiplication, ce qui le rend obsolète dans ce contexte.

L'idée du chiffrement homomorphe a été évoquée pour la première fois dans le contexte du chiffrement à clé publique par Rivest, Adleman et Dertouzos [45] en 1978. Les restrictions rencontrées dans les chiffrements homomorphes ont conduit à les classer en trois groupes [2] : Le chiffrement partiellement homomorphe (PHE) qui permet un seul type d'opération (l'addition ou la multiplication) avec un nombre illimité de fois, le chiffrement quelque peu homomorphe (SWHE) qui permet certains types d'opérations (l'addition et la multiplication) en un nombre limité et le chiffrement totalement homomorphe (FHE) proposé par Craig Gentry [32] qui permet tous les types d'opérations (l'addition et la multiplication) avec un nombre illimité de fois. Ce qui a constitué la première génération de cryptosystèmes FHE. Dès lors s'en est suivi depuis 2010, la deuxième, la troisième et la quatrième génération de cryptosystèmes FHE. Chaque nouvelle génération est une amélioration de l'ancienne, mais chacune garde son intérêt, notamment selon le type de donnée que l'on souhaite traiter. De manière chronologique, nous avons : le cryptosystème DGHV (de van Dijk, Gentry, Halevi, et Vaikuntanathan) en 2010, le cryptosytème BGV (Brakerski-Gentry-Vaikuntanathan) en 2011, les cryptosystèmes de LTV (Lopez-Alt, Tromer et Vaikuntanathan ) et BFV (Brakerski/Fan-Vercauteren) en 2012, le cryptosystème de BLLN (Bos, Lauter, Loftus, et Naehrig) en 2013, le cryptosystème de GSW (Craig Gentry, Amit Sahai, et Brent Waters) en 2013 et le cryptosystème CKKS (Cheon-Kim-Kim-Song) en 2016. La sécurité de la plupart de ces cryptosystèmes est basée sur la difficulté à résoudre le problème du (Ring) Learning With Errors (RLWE)[50] qui est un problème difficile basé sur les réseaux euclidiens capable de résister aux attaques quantiques. La mise en oeuvre de solution de chiffrement homomorphe est complexe, et nécessite une très bonne compréhension des principes mathématiques sous-jacents. Ainsi, pour faciliter leur utilisation en pratique, ces cryptosystèmes sont implémentés dans des bibliothèques logicielles et standardisés [6] par des groupes de chercheurs afin de permettre aux dévoloppeurs de les utiliser avec plus de souplesse.

En informatique, une bibliothèque ou librairie logicielle (ou encore, bibliothèque de programmes) est un ensemble de fonctions utilitaires, regroupées et mises à disposition afin de pouvoir être utilisées sans avoir à les réécrire. Ainsi, une bibliothèque homomorphique logicielle qui permet d'effectuer

LISTE DES TABLEAUX 3

Mémoire de Master 2 Recherche 3 MOUYOUME DIEUDONNE(c) UYI

des calculs sur des données chiffrées de manière homomorphe et sécurisée. Dès lors, il se pose un problème de comparaison des bibliothèques FHE qui en raison de leurs différents coûts de calculs, peuvent guider les devéloppeurs à utiliser l'une au détriment de l'autre. C'est dans ce contexte que se situe notre travail de recherche.

Problématique

Dans le contexte de l'émergence du chiffrement homomorphe (CH), une technologie révolutionnaire permettant d'exécuter des opérations complexes sur des données chiffrées sans compromettre leur confidentialité, il devient crucial d'évaluer l'efficacité opérationnelle des implémentations logicielles existantes. Une analyse comparative s'impose entre les bibliothèques Microsoft SEAL, OpenFHE et PALISADE, supportant les cryptosystèmes BGV (Brakerski-Gentry-Vaikuntanathan) et BFV (Brakerski-Fan-Vercauteren).

Question de recherche

Question générale de recherche

La question de recherche qui découle de cette problématique est la suivante:

Quelle bibliothèque, parmi Microsoft SEAL, OpenFHE et PALISADE, optimise le plus efficacement les temps de calcul associés aux phases critiques du traitement homomorphe -- chiffrement, multiplication homomorphique et déchiffrement -- lors de l'exécution d'une multiplication matricielle, tout en respectant les garanties de sécurité des cryptosystèmes BGV/BFV?

Questions spécifiques de recherche

De cette question générale de recherche découle ces quatre questions spécifiques ci-dessous:

· Quels schémas (FHE, PHE, SHE) sont adaptés à quels cas d'usage?

· Quels sont les impacts des schémas de chiffrement homomorphe (FHE, PHE, SHE) sur l'ex-pansion des données, et comment les compromis entre sécurité et efficacité spatiale varient-ils selon les cas d'usage?

· Comment les choix de paramétrisation des cryptosystèmes (BGV, BFV) modulent-ils les latences induites par les opérations homomorphiques (addition, multiplication) dans les bibliothèques FHE (SEAL, OpenFHE et PALISADE)?

· Quelles classes de problèmes (traitement d'images, agrégation de données, ML confidentiel) justifient l'adoption de FHE, SHE ou PHE, et selon quels critères opérationnels (budget calcul, tolérance au bruit)?

LISTE DES TABLEAUX 4

Mémoire de Master 2 Recherche 4 MOUYOUME DIEUDONNE(c) UYI

Objectif spécifique de la recherche

À partir de cet objectif général, notre objectif spécifique est de procéder à une analyse comparative de ces bibliothèques afin de déterminer laquelle présente les performances les plus optimales pour le chiffrement, la multiplication homomorphe et le déchiffrement.

Intérêt de l'étude

La comparaison des performances des bibliothèques homomorphiques revêt un intérêt majeur pour plusieurs acteurs impliqués dans le domaine du chiffrement homomorphe. Tout d'abord, les dé-veloppeurs qui cherchent à intégrer des fonctionnalités de calculs sur des données chiffrées dans leurs applications ont besoin d'informations sur les performances des bibliothèques disponibles afin d'uti-liser la plus adaptée à leurs besoins spécifiques. De plus, les chercheurs travaillant sur l'amélioration des cryptosystèmes de chiffrement homomorphe peuvent tirer parti de ces comparaisons pour identifier les aspects à optimiser.

Les praticiens du domaine, tels que les experts en cybersécurité, peuvent utiliser ces informations pour proposer des solutions appropriées aux entreprises et aux organisations qui cherchent à mettre en oeuvre le chiffrement homomorphe.

En fin, malgré les nombreux avantages du chiffrement homomorphe, le coût (temps de calcul) des différentes opérations (addition, multiplication) reste un problème crucial, d'où l'intérêt à les comparer.

Structure du mémoire

Ce mémoire est organisé, hors mis l'introduction générale, en cinq chapitres comme suit:

· Le chapitre 1

Ce chapitre porte sur les généralités.

· Le chapitre 2

Ce chapitre est consacré sur l'état de l'art du chiffrement homomorphe.

· Le chapitre 3

Ce chapitre porte sur les systèmes de calculs homomorphes

· Le chapitre 4

Ce chapitre porte sur l'étude de l'existant sur la comparaison des bibliothèques FHE

· Le chapitre 5

Ce chapitre porte sur l'implémentation et les résultats.

Chapitre I

Un groupe est un ensemble G muni d'une loi de composition interne notée multiplicativement * tel que :

· la loi * soit associative :(x * y) * z = x * (y * z),

· la * possède un élément neutre e E G : Vx E Gx * e = e * x = x,

· tout élément x E G possède un symétrique (ou inverse) pour *, noté x^-1, satisfaisant x*x^-1 = x-1 * x = e.

Définition 1.1.1 (Groupe)

· Si de plus,Vx, y E G , on a alors x * y = y * x est dit commutatif (ou abélien)

GENERALITES

Ce chapitre porte sur les généralités des notions mathématiques liées au chiffrement homomorphe.

1.1 Notions mathématiques

Dans cette sous section nous présentons les notions essentielles sur les structures algébriques utiles pour comprendre le chiffrement homomorphe.

1.1.1 Structures algébriques

Soit (G, *) un groupe et H une partie de G. On dit que (H, *) est un sous-groupe de G si :

· H est stable pour la loi *

· (H,*) lui-même est un groupe.

Définition 1.1.2 (Sous-groupe)

Mémoire de Master 2 Recherche 5 MOUYOUME DIEUDONNE(c) UYI

1.1 Notions mathématiques 6

Définition 1.1.6 (Corps)

Un corps est un anneau commutatif dans lequel tout élément non nul est inversible.

Si H est un sous-groupe de (G, *) si et seulement si :

· H contient l'élément neutre du groupe;

· Vx,y E H, x * y^-1 E H.

Proposition 1.1.1

un homomorphisme est une application f : (G, *) -- (G^', *) , entre deux groupes (G, *) et (G^', *) , qui vérifie :

V(g, h) E G², f(g * h) = f(g) * f(h).

Définition 1.1.3 (Homomorphisme de groupe)

Un anneau est la donnée d'un ensemble A et de deux lois de composition interne notées + et x sur A vérifiant les propriétés suivantes :

· (A, +) est un groupe abélien dont le neutre est noté 0A ;

· La loi x est associative : pour tous x, y et z de A, x x (y x z) = (x x y) x z,

· La multiplication x est distributive par rapport à + : pour tout élément x,yetz,xx(y+z)=(xxy)+(xxz)et(x+y)xz=(xxz)+(yxz).

· la loi x possède un élément neutre noté 1A ;

Lorsque la loi x est commutative, on dit que l'anneau A est commutatif.

Définition 1.1.4 (Anneau)

I c A est un idéal d'un anneau commutatif (A, +, *) si et seulement si :

(I, +) est un sous-groupe additif de (A, +)

Va E A,Vx E I,a * x E I

Définition 1.1.5 (Idéal d'un anneau)

Mémoire de Master 2 Recherche 6 MOUYOUME DIEUDONNE(c) UYI

1.1 Notions mathématiques 7

Définition 1.1.7 (Corps d'un polynôme)

Si (V[X], +, X) est un anneau commutatif unitaire et P E V[X] un polynôme irréductible, alors V[X]/(P) est un corps

1.1.2 Problèmes difficiles sur les entiers

Problème 1.1.1 (Factorisation d'entier)

Étant donné un entier naturel n = pq, avec p et q premiers, retrouver p et q

Résoudre ce problème est simple lorsque le nombre n est petit.

Étant donné (n, e, y) avec y E (7L/n7L)^* et n = pq trouver x tel que y [x^e]_n.

Un nombre n de la forme pq où p et q sont deux grands nombres premiers est appelé un module RSA.

Problème 1.1.2 (RSA)

L'algorithme de chiffrement RSA a été inventé par Ron Rivest, Adi Shamir et Leonard Adleman en 1977. Il fut l'un des premiers algorithmes de chiffrement dit à clé publique, c'est-à-dire que le chiffrement d'un message ne requiert pas que l'expéditeur partage un secret avec le destinataire. Il est devenu, depuis, l'un des algorithmes de chiffrement et d'authentification les plus utilisés au monde.

Problème 1.1.3 (Logarithme discret (DLP) dans ?/p?)

Étant donné un nombre premier p, un élément générateur g qui engendre tout le groupe, et un élément cible h, calculer un entier x, 0 < x < p tel que g^x = h.

Mémoire de Master 2 Recherche 7 MOUYOUME DIEUDONNE(c) UYI

On parle de logarithme, car c'est une fonction inverse de l'exponentiation, discret, car il prend des valeurs entières, entre 0 et p - 1.

En 1976, W. Diffie et M. Hellman publient un schéma d'échange de clé qui n'a pas besoin de secret commun préalable. Il repose sur la difficulté de calculer un logarithme discret. Ici aussi, on manipule des entiers, modulo un nombre premier p.

1.1 Notions mathématiques 8

Soit les éléments non nuls (entre 1 et p - 1, p premier), on peut trouver un générateur g parmi eux, tel que g, g², g³, ... , gp^-1 = [1]_p prennent toutes les valeurs possibles entre 1 et p - 1. Ce sous-ensemble est appelé un groupe cyclique. On dit que (7L/p7L)^*, muni de la multiplication est un groupe cyclique.

Définition 1.1.8 (Groupe cyclique dans (7L/p7L)^*)

Plus simplement, deux entités A et B s'accordent sur un nombre premier p tel que (p-1)/2 est premier, et un générateur g. A choisit au hasard un entier a entre 1 et p - 1, de même B choisit au hasard un entier b dans cet intervalle. A envoie g^a mod p à B et B envoie g^b mod p à A. Puis A connaissant gb et a, calcule (g^b)^a modp , et de même B peut calculer (g^a)^b mod p. Par la suite A et B connaissent le secret g^ab . Un attaquant qui peut lire les communications ne connaît que p, g, ga, g^b et ne peut pas calculer g^ab, mais seulement g^a+b . Cette difficulté de casser ce schéma a été formalisée comme suit.

Problème 1.1.4 (Diffie-Hellman)

Étant donné un nombre premier p définissant 7L/p7L, et un générateur g du groupe, pour (g, g^x, gy) avec x, y inconnus, calculer g^xy .

Soit n > 1, un entier positif et x E (7L/n7L)^* tel que pgcd(x, n) = 1

On dit que x est un résidu quadratique modulo n si 3y E (7L/n7L)^* tel que y² = [x]_n Si un tel y n'existe pas, x est un non-résidu quadratique modulo n.

Définition 1.1.9 (Résidu quadratique)

Soit p un premier. Pour un entier a, on définit le symbole de Legendre par :

Définition 1.1.10 (Symbole de Legendre)

! x = n

? ? ?????

??????

x si x divise n

1 si x est un residu quadratique mod n -1 sinon.

Si l'on sait calculer efficacement un logarithme discret, alors cela permet de résoudre le problème de Diffie-Hellman.

Mémoire de Master 2 Recherche 8 MOUYOUME DIEUDONNE(c) UYI

1.1 Notions mathématiques 9

Problème 1.1.5 (Résidualité quadratique)

Consiste à déterminer si un élément de (Z/nZ)^* est un résidu quadratique.

Ce problème est considéré comme étant calculatoirement difficile dans le cas général et sans information supplémentaire. Par conséquent, il s'agit d'un problème important en cryptographie où il est utilisé comme hypothèse calculatoire.

Étant donné S = {s1,.. . , s_n} un grand ensemble d'entiers, t E Z, trouver un sous-ensemble S^' de

XS tel que

xiES

Problème 1.1.6 (Sparse Subset Sum Problem(SSSP))

xi = t

Le problème de la somme de sous-ensembles est un problème classique en informatique théorique et en cryptographie. Il consiste à déterminer s'il existe un sous-ensemble d'éléments, dans un ensemble donné d'entiers, dont la somme est égale à une valeur cible spécifique.

Étant donné un ensemble {x1 . . . , x_ô} dans lequel xi = p.qi + ri pour 1 < i < ô, retrouver p Pour un entier pair, on utilise la distribution suivante sur des entiers de ã-bits

Dã,ñ(p) = {q.p + r, q E [0, 2ã/p], r E [-2ñ, 2ñ]}

Problème 1.1.7 (Approximate-Greatest Common Divisor Problem(AGCD))

Soit X un ensemble fini. Une distribution sur X est dite uniforme si la probabilité de x E X est

égale à ¹

card(X).

La distribution uniforme sur X est notée U(X)

Définition 1.1.11 (Distribution uniforme discrète)

L'idée est que la somme de deux nombres proches d'un multiple de p est également proche d'un multiple de p, de même pour le produit.

1.1.3 Distributions de probabilités

Les distributions sont généralement utilisées sur les algorithmes de chiffrement homomorphe.

Mémoire de Master 2 Recherche 9 MOUYOUME DIEUDONNE(c) UYI

1.1 Notions mathématiques 10

Une distribution gaussienne d'écart-type ó et de centre c est une distribution sur dont la probabilité de x E est:

Définition 1.1.12 (Distribution gaussienne discrète)

e

Dó,c(x) = P kE e-( k-c

2ó )2

-( x-c 2ó )2

Mémoire de Master 2 Recherche 10 MOUYOUME DIEUDONNE(c) UYI

FIGURE 1.1 - La distribution normale réduite avec les aires centrales autour de 1 et 2 écarts types mises en évidence

1.1.4 Problèmes sur les réseaux euclidiens

L'étude des réseaux euclidiens en mathématiques remonte au XVIII^e siècle, lorsque Leonhard Euler a commencé à explorer les structures géométriques des points dans l'espace. Cependant, ce n'est qu'au XX^e siècle que le concept de réseaux euclidiens a trouvé une application en cryptographie. Dans les années 1990, des chercheurs tels qu'Ajtai, Dwork, Regev et d'autres ont introduit la notion de réseaux euclidiens comme base de problèmes complexes en cryptographie, ouvrant ainsi la voie à de nouvelles constructions cryptographiques.[12].

1.1 Notions mathématiques 11

Un réseau euclidien L de dimension n est un sous-groupe discret de (Rⁿ, +).

L(b1, b2, . . . , bd) = {x ? Rⁿ, x =

Définition 1.1.13 (Réseau euclidien)

_Xd

i=1

(xibi), xi ? Z}.

Un réseau euclidien est donné par une base B = (b1, b2,. . . , bd) de vecteurs de Rⁿ telle que tout vecteur du réseau est une combinaison linéaire à coefficients entiers des vecteurs de B. Dans la pratique, un réseau L de rang d est représenté par l'une de ses bases B = (b1, b2,.. . , bd) écrite sous forme d'une matrice appartenant à R^d×n, les lignes de la matrice sont les coordonnées des vecteurs de la base.

FIGURE 1.2 - Exemple d'un réseau euclidien

Définition 1.1.14 (Rang du réseau)

On appele le rang du réseau L, le nombre d'élément dans une base de L

Définition 1.1.15 (Distance minimale d'un réseau)

La distance minimale d'un réseau est ë1(L) := minv?L\{0}(?v?2)

Soit L un réseau de dimension n, on a : ë1(L) = n * (?detL?)¹/ⁿ

Théorème 1.1.1 (Théorème de Minkowski)

Mémoire de Master 2 Recherche 11 MOUYOUME DIEUDONNE(c) UYI

1.1 Notions mathématiques 12

ë1 a un intérêt particulier car il fournit une norme par laquelle nous pouvons évaluer la longueur des vecteurs dans un réseau.

Soit V un sous-espace vectoriel de dimension n et (b1,. . . , b_n) une base de V . On considère la famille de vecteurs (b^* ₁,. . . , b^* _n) définie par:

?bi, b* i ? ?b^* j, b^* _j?

Alors (b^* ₁,. . . , b^* _n) est une base orthogonale de l'espace de V

avec pour j < i

Théorème 1.1.2 (Méthode d'orthogonalisation de Gram-Schmidt)

b* i = bi,b* 1 = bi -

ui,j =

_Xi- 1

j=1

ui, jb* j

Mémoire de Master 2 Recherche 12 MOUYOUME DIEUDONNE(c) UYI

FIGURE 1.3 - Un réséau engenré par la mauvaise base (b1, b2)[42]

FIGURE 1.4 - Même réséau engenré par bonne base (u1, u2)[42]

Les problèmes mathématiques liés aux réseaux euclidiens trouvent des applications remarquables en cryptographie. Ces problèmes ont été introduits en 1996 par le mathématicien Hongrois Miklós Ajtai [5] et ont rapidement gagné en popularité.

L'un de ces problèmes, sans doute l'un des plus célèbre de part ses applications est le problème du vecteur le plus proche.

1.1 Notions mathématiques 13

Étant donné une base B = (b1, b2,. . . , bd) d'un réseau euclidien de L et un vecteur t ? Zⁿ, trouver

un vecteur v =

Problème 1.1.8 (Vecteur le plus proche)

_Xd i=1

xibi ? n tel que ?t -

_Xd i=1

xibi? soit minimale.

Le problème du plus proche [34][37] ( CVP pour Le Closest Vector Problem) consiste à trouver le vecteur d'un réseau euclidien L le plus proche d'un point donné dans l'espace euclidien.

FIGURE 1.5 - Le CVP

Source https :// vozec.fr/other/lattice-introduction/cvp.png

Dans la pratique, il est possible de tranformer le problème du vecteur le plus proche en un atre problème similaire et tout aussi célèbre appelé le problème du plus court vecteur.

Étant donné une base B = (b1, b2,. . . , bd) d'un réseau euclidien de L, trouver un vecteur non nul

v =

Problème 1.1.9 (Plus court vecteur)

_Xd i=1

xibi ? n tel que ?

_Xd i=1

xibi? soit minimale.

Mémoire de Master 2 Recherche 13 MOUYOUME DIEUDONNE(c) UYI

Le problème du plus court vecteur (SVP pour Short Vector Problem) consiste à trouver le vecteur le plus court (le plus petit en norme euclidienne) d'un réseau euclidien.

1.1 Notions mathématiques 14

Mémoire de Master 2 Recherche 14 MOUYOUME DIEUDONNE(c) UYI

Figure 1.6 - Le SVP

Source https :// vozec.fr/other/lattice-introduction/svp.png

Algorithmes de réduction

Les algorithmes de réduction tels que LLL et BKZ sont utilisés pour résoudre efficacement le CVP et le SVP. En effet, ils permettent de transformer la réseau dans une meilleure base avec des vecteurs orthogonaux et plus petits.

1. Algorithme LLL (Lenstra-Lenstra-Lovász)

En 1982, Lenstra, Lenstra et Lovász[42] ont inventé un algorithme très efficace pour la réduction des réseaux ayant des dimensions supérieures. Il prend en entrée une base quelconque (b1,. . . , b_n) et la transforme en une base presque orthogonale, en réduisant la taille des vecteurs.

L'idée principale de l'algorithme LLL est de remplacer les vecteurs de la base qui ne sont pas "presque orthogonaux" par des combinaisons linéaires entières de ces vecteurs. L'algorithme s'exécute en temps polynomial.

Algorithm 1 Réduction LLL (Lenstra-Lenstra-Lovász)

_i1 [

Entrée : Base B = {b1, . . . , b_n} ? ^m, ä ? ₄, 1

Sortie : Base LLL-réduite

Calculer la base orthogonale {u1,.. . , u_n} par Gram-Schmidt i ? 2

tant que i = n faire

pour j = i - 1 to 1 faire

ui, j ? ?uj,uj? bi ? bi - ?ui_, j? · bj Mettre à jour ui

?bi,uj?

si ä?ui-1?² > ?ui + ui,i-1ui-1?² alors

Échanger bi et bi-1 i ? max(i - 1,2)

sinon

i ? i + 1

Retouner : B

La complexité de l'algorithme LLL est: O(d⁶ log³ T) avec T = ||bi|| pour tout i

2. Algorithme BKZ (Block Korkine-Zolotarev)

L'algorithme BKZ introduit en 1987 [40] est une amélioration de l'algorithme LLL. Il utilise une

1.1 Notions mathématiques 15

approche en blocs pour obtenir une réduction plus forte des vecteurs dans le réseau euclidien. L'algo-rithme BKZ est plus efficace que LLL pour les instances difficiles, mais il est également plus coûteux en temps de calcul.

Algorithm 2 Réduction BKZ (Block Korkine-Zolotarev)

Entrée : Base B = {b1,. . . ,b_n} ? Z^m, taille de bloc â = 2, paramètre ô ?]¹ ₄, 1[ Sortie : Base BKZ-réduite

Appliquer LLL(B, ô) sur toute la base; k ? 1

tant que k = n - 1 faire

q?min(k+â-1,n)Bbl_oc ?{bk,...,b_q}

Bréduit ? LLL(Bbloc, ô) v ? EnumérerVecteurMin(B_réd_uit) si ?v? < ?bk? alors

Remplacer bk par v dans B

Appliquer LLL(B, ô) localement autour de k k?max(k- 1,1)

sinon

Appliquer LLL(B, ô) sur {bk,. . . , b_q} k ? k + 1

Retouner: B

La complexité de l'algorithme BKZ est O(ⁿ²

â2 logⁿ)

Étant donné un paramètre fixé n = 1, un module q = 2, une distribution d'erreur X d'écart type ó. Le problème LWE consiste à trouver S ? Zn q à partir de m échantillons (Ai, < Ai, S > +Ei) où les Ai sont des vecteurs tirés uniformément de Zm q × Zn q et les Ei sont des erreurs tirées d'une distribution

gaussienne X sur Zⁿ _q.

Problème 1.1.10 (LWE -Apprentissage avec erreur)

Mémoire de Master 2 Recherche 15 MOUYOUME DIEUDONNE(c) UYI

Le problème d'apprentissage avec erreur (LWE pour Learning With Errors) introduit en 2005 par Oded Regev [44] est un des problèmes difficile sur lequel reposent plusieurs cryptosystèmes à base de réseaux euclidiens. Le problème Learning with errors (LWE) consiste à trouver un secret masqué au milieu d'équations linéaires bruitées.

Exemple 1.1.1. Système linéaire du problème LWE

???????????????????????????????

×

???????????????

6 9 11 11

???????????????

+

???????????????????????????????

0 -1 1 -1 1 0 -1

???????????????????????????????

=

???????????????????????????????

4 7 2 1 5 12 8

???????????????????????????????

???????????????????????????????

4 1 11 10 5 5 9 5 3 9 0 10 6 9 0 2 12 7 3 2 6 5 11 4 3 3 5 0

1.1 Notions mathématiques 16

Il s'agit de trouver le sécret s dans (Z/13Z)⁴

Soit un entier d = 2^k, k > 2 et q un module premier tel que q 1 mod 2?(d) avec ?(d) = 2^k-1. On définit R_q = Z_q[x]/(x^d + 1) un anneau de polynôme.

Étant donné un secret S E R_q, on construit m échantillons (A, B) = (A, A.S + E) E R_q X R_q oÙ A est tiré uniformément de R_q et E est un terme d'erreur choisi indépendamment d'une certaine distribution d'erreur sur R_q .

Le problème RLWE consiste à trouver S à partir des échantillons.

Problème 1.1.11 (Ring-LWE-Apprentissage avec erreurs sur les anneaux)

Mémoire de Master 2 Recherche 16 MOUYOUME DIEUDONNE(c) UYI

Le problème de l'apprentissage avec erreurs sur les anneaux (Ring-LWE pour Ring Learning With Error), introduit par Stehlé, Steinfeld, Tanaka et Xagawa dans [50] est le problème LWE dans un anneau de polynômes.

Mémoire de Master 2 Recherche 17 MOUYOUME DIEUDONNE(c) UYI

Chapitre II

ETAT DE L'ART DU CHIFFREMENT HOMOMORPHE

Dans ce chapitre nous parlons des algorithmes d'un système de chiffrement homomorphe, des types de chiffrements homomorphes, les générations du chiffrement homomorphe, les cryptosystèmes basés sur le problème R-LWE, les applications,les avantages et les limites du FHE.

2.1 Chiffrement homomorphe

Les données existent sous trois états : au repos (stockées), en transit (en transfert) et en utilisation (en traitement). Le chiffrement classique protège efficacement les données au repos et en transit, car leur valeur reste stable après déchiffrement. En revanche, les données en utilisation posent un problème majeur: toute opération mathématique (addition, multiplication, etc.) sur des données chiffrées modifie irrémédiablement le résultat final. Cela crée un risque de fuite d'informations, car les relations entre texte clair et texte chiffré pourraient être déduites par un observateur externe.

Un bon algorithme de chiffrement doit rendre le texte chiffré indiscernable d'une suite aléatoire, éliminant toute trace du texte clair original. Cependant, pour permettre des calculs sur données chiffrées, une relation mathématique entre clair et chiffré doit exister en secret. Cette exigence contradictoire - détruire les relations visibles tout en préservant des liens cachés - représente un défi technique majeur. C'est ici qu'intervient le chiffrement homomorphe, qui résout ce paradoxe en permettant des opérations directes sur les cryptogrammes tout maintenant une sécurité robuste.

Le chiffrement homomorphe autorise des calculs complexes (comme l'analyse statistique ou le machine learning) sur des données jamais déchiffrées. Par exemple, un serveur cloud peut traiter des données médicales chiffrées sans y accéder, et seul le propriétaire de la clé peut décrypter le résultat. Cette technologie repose sur des schémas mathématiques avancés (comme les réseaux euclidiens ou les problèmes de log discret) qui masquent les relations entre opérations chiffrées et résultats. Bien que coûteuse en calculs, elle ouvre des perspectives inédites pour la confidentialité dans le cloud, les votes électroniques vérifiables, ou la recherche collaborative sur données sensibles.[24].

2.1 Chiffrement homomorphe 18

Mémoire de Master 2 Recherche 18 MOUYOUME DIEUDONNE(c) UYI

2.1.1 Algorithmes d'un système de chiffrement homomorphe

Les algorithmes de chiffrement homomorphes sont un type d'algorithme de chiffrement conçu

pour permettre d'effectuer des opérations mathématiques sur les données chiffrées. Il s'agit d'une

propriété extrêmement utile qui trouve de nombreuses applications.

Étant donné C1, C2 ? C l'espace des chiffrés, m ? M l'espace des messages clairs, et F l'espace

des fonctions évaluables, on définit un chiffrement homomorphe sur F le quadruplet d'algorithmes

(Key,Enc,Dec, Eval) [32][41]tel que:

-- Key : N ? PK × S K : la fonction de génération des clefs;

-- Enc : M ? C est la fonction de chiffrement;

-- Dec : C ? M est la fonction de déchiffrement;

-- Eval : F × C × C ? C est la fonction d'évaluation.

On souhaite avoir les propriétés suivantes:

1 La correction :Dec(Enc(m)) = m;

2 L'homomorphisme :?f ? F, D_ec(Eval(f, C1, C2)) = f(D_ec(C1), Dec(C2)).

Un exemple d'application simple du chiffrement homomorphe est utilisé dans le traitement des données dans le cloud (voir Figure 2.1). Le client chiffre ses données et les envois au serveur cloud qui effectue le calcul homomorphe sur les données chiffrées sans en connaître le résultat. Ce résultat est envoyé au client qui le déchiffrement avec sa clé sécrète.

FIGURE 2.1 - Simple scénario fondé sur le chiffrement homomorphe dans le could

2.1.2 Types de chiffrements homomorphes

L'objectif du chiffrement homomorphe est de créer un algorithme de chiffrement qui permette un nombre infini d'additions ou de multiplications des données chiffrées. À la fin du processus, le résultat doit être le texte chiffré qui serait produit si les mêmes opérations étaient effectuées sur les textes clairs correspondants et que le résultat était chiffré.

Un cryptosystème peut être homomorphe pour la multiplication,sans l'être pour l'addition ou inversement. Il est également possible que la profondeur des opérations prise en charge soit limitée.

2.1 Chiffrement homomorphe 19

Mémoire de Master 2 Recherche 19 MOUYOUME DIEUDONNE(c) UYI

Par exemple, un système peut être homomorphe à la fois pour l'addition et la multiplication, mais seulement pour un nombre limité d'opération. Enfin, il est possible qu'un système conserve toutes ses caractéristiques, c'est-à-dire qu'il prenne en charge à la fois la multiplication et l'addition un nombre infini de fois. Ces différentes possibilités ont conduit à classer les systèmes de chiffrement homomorphe en trois catégories[2] :

-- Le chiffrement partiellement homomorphe (PHE pour Partial Homomorphic Encryption),

-- Le chiffrement quelque peu homomorphe (SWHE pour Somewhat Homomorphic Encryption),

-- Le chiffrement totalement homomorphe (FHE pour Fully Homomorphic Encryption).

2.1.2.1 Le chiffrement partiellement homomorphe

Il s'agit de systèmes de chiffrement qui ne prennent homomorphiquement en charge qu'un seul type d'opération (l'addition ou la multiplication) mais sans restriction quant à la complexité des expressions. La correspondance entre le texte clair et le texte chiffré préserve la profondeur structurelle, mais pas l'étendue des opérations possibles. Cela permet d'effectuer un nombre infini d'opérations précises sur des données chiffrées. Quand le type d'opération est l'addition, on parle d'homomor-phisme additif, et d'homomorphisme multiplicatif quand l'opération est la multiplication.

Comme exemples de cryptosystèmes partiellement homomorphe, on peut citer RSA [45],Paillier [43]et ElGamal [26].

2.1.2.2 Le chiffrement quelque peu homomorphe

Il s'agit de systèmes de chiffrement qui prennent homomorphiquement en charge n'importe quel type d'opération ( l'addition et la multiplication) mais seulement jusqu'à une certaine profondeur des opérations. La correspondance entre le texte clair et le texte chiffré préserve l'étendue structurelle, mais pas la profondeur des opérations possibles. Cela permet d'effectuer un nombre limité de toute opération sur des données chiffrées.

Comme exemple de cryptosystèmes quelque peu homomorphe on peut citer le cryptosystème DGHV.

2.1.2.3 Le chiffrement totalement homomorphe

Ce sont de systèmes de chiffrement qui supportent toutes sortes d'opérations, sans limitation quant à la profondeur des opérations. Il n'y a pas de correspondance entre le texte clair et le texte chiffré qui permet au chiffrement totalement homomorphe de conserver à la fois l'étendue et la profondeur des opérations possibles. C'est plutôt une méthode particulière qui permet de dépasser les limites d'un chiffrement quasi homomorphe. Les systèmes de chiffrement totalement homomorphe peuvent réaliser un nombre infini d'opérations sur les données chiffrées grâce à la technique appelée le boots-rapping ou le réamorçage consiste à « rafraîchir » le bruit accumulé dans un texte chiffré en le chiffrant à nouveau avec la clé publique et en évaluant ensuite de manière homomorphe sa fonction de déchiffrement à l'aide du chiffrement de sa clé privée sous la clé publique.

2.2 Générations du chiffrement homomorphe 20

Mémoire de Master 2 Recherche 20 MOUYOUME DIEUDONNE(c) UYI

TABLE 2.1 - Types de chiffrement homomorphe

Type de chiffrement	Opérations prises en charge	Nombre d'opérations
Partiellement homomorphe	Type unique (addition ou multiplication)	Infini
Quelque peu homomorphe	Tout type (addition et multi- plication)	Limité
Totalement homomorphe	Tout type (addition et multi- plication)	Infini

2.2 Générations du chiffrement homomorphe

Au fil des années, des tentatives ont été entreprises pour mettre en oeuvre le FHE, mais sans succès. Toutefois, Craig Gentry a présenté le premier système de chiffrement entièrement homomorphe en octobre 2009 [32], ce qui représente une avancée majeure dans ce domaine. Il est l'auteur de la première génération de cryptosystèmes FHE. Par la suite, depuis 2010, il y a eu une deuxième, une troisième, puis une quatrième génération de cryptosystèmes FHE. Chaque génération est un progrès de la précédente, mais chacune conserve son intérêt, en fonction du type de données que l'on souhaite traiter.

2.2.1 Pré-FHE

L'idée selon laquelle le chiffrement homomorphe pourrait être utilisé pour protéger les données existe depuis des décennies. Le problème de la création d'un chiffrement complètement homomorphe a été proposé pour la première fois en 1978 [45]. Des fonctions de chiffrement spéciales privées « homomorphismes privés » ont été proposées. Au cours de cette période, plusieurs solutions partielles ont été développées à l'instar du :

-- Cryptosystème RSA (nombre illimité de multiplications modulaires);

-- Cryptosystème ElGamal(nombre illimité de multiplications modulaires);

-- Cryptosystème Goldwasser-Micali (nombre illimité d'opérations XOR);

-- Cryptosystème Benaloh (nombre illimité d'ajouts modulaires);

-- Cryptosystème Paillier(nombre illimité d'ajouts modulaires);

-- Cryptosystème Boneh-Goh-Nissim (nombre illimité d'opérations d'addition, mais maximum une multiplication)

.

[
·] Cryptosystème RSA

Le système de chiffrement RSA a été inventé par Ron Rivest, Adi Shamir et Len Adleman [45], en 1978. C'est un des cryptosystèmes asymétrique les plus connus et utilisés aujourd'hui. Il est basé sur le problème de factorisation d'entiers (voir problème 1.1.1).

2.2 Générations du chiffrement homomorphe 21

Mémoire de Master 2 Recherche 21 MOUYOUME DIEUDONNE(c) UYI

Génération des clés

-- Générer deux grands nombres premiers, p et q, de même taille, et tel que leur produit

n = p.q fasse le nombre de bits requis

-- Calculer n = p X q et ?(n) = (p - 1)(q - 1)

-- Choisir un entier e tel que 1 < e < ?(n) et tel que pgcd(e, ?(n)) = 1

-- Calculer l'exposant secret d, tel que 1 < d < ?(n) et tel que e X d = [1]?(n)

-- La clé publique est: (n, e)

-- La clé secrète est: (d, p, q)

Chiffrement

-- Le message chiffré est: Enc(m) = c = [m^e]_n

Déchiffrement

-- Pour déchiffrer le message, on calcule m = [c^d]_n

Homomorphisme

Soient m1 et m2 deux messages à chiffrer tel que Enc(m1) = [m^e _1]n et Enc(m2) = [m^e _2]n alors

Enc(m1) X Enc(m2) = ([m^e 1]n)([me 2]n)

= [(m1 X m2)^e]_n = Enc(m1 X m2)

[
·]Cryptosystème ElGamal

Le chiffrement ElGamal a été inventé par Taher ElGamal en 1985 [26]. Il représente l'alternative la plus courante au chiffrement RSA. il est basé sur le problème du logarithme discret( voir problème 1.1.3).

Génération des clés

-- Choisir un générateur g d'ordre très grand d'un groupe cyclique (7L/p7L)^*, p premier

-- Choisir 1 < a < p - 1 tel que a E 7L/q7L

-- Calculer A = [g^a]_p

-- La clé publique est (7L/p7L)^*, p, g, A)

-- La clé secrète est a

2.2 Générations du chiffrement homomorphe 22

Mémoire de Master 2 Recherche 22 MOUYOUME DIEUDONNE(c) UYI

Chiffrement

Pour chiffrer un message m, on choisit une clé éphémère k

On calcule c1 = [g^k]_p et c2 = [m.A^k]_p et on renvoie le chiffré Enc(m) = (c1, c2)

Déchiffrement

Pour déchiffrer, il suffit de calculer :

m = c2

Homomorphisme

Soit Enc(m1) et Enc(m2)) les chiffrés des messages m1 et m2 Enc(m1) x Enc(m2) = (g^k^1, m1.A^k^1).(g^k^2, m2.A^k^2) = (g^k^1+k2, (m1.m2).A^k^1+k2) = Enc(m1 x m2).

[
·]Cryptosystème de Goldwasser-Micali

Goldwasser et Micali [46] ont proposé en 1982 le premier système de chiffrement probabiliste, à clé publique, basé sur le problème de la résidualité quadratique( voir problème 1.1.5), et permettant de chiffrer des nombres binaires.

Génération des clés

Choisir aléatoirement deux grands nombres premiers p et q.

Calculer n = p.q.

Choisir x E {1, ... , n - 1} tel que (^x_p) = -1 et (^x_q) = -1

La clé publique est (x, n), la clé privée est (p, q).

Chiffrement

Pour chiffrer un message m = (m1, ... , mk) E {0,1}^kconstitué de k bits Pour tout i = 1, ... , k Choisir aléatoirement ri E (7L/n7L)^* Définir ci = [r^2i .x^mi]n Le chiffré de m est c = (c1, ... , ck) E (7L/n7L)^k

2.2 Générations du chiffrement homomorphe 23

Mémoire de Master 2 Recherche 23 MOUYOUME DIEUDONNE(c) UYI

Déchiffrement

Pour déchiffrer c = (ci,.. . , ck) E (1/p1)^k Pour tout i = 1,.. . , k : -- on calcule a = [ci]p -- Si a est un carré modulo p, on affecte mi = 0 -- Sinon, on affecte mi = 1 -- Le message déchiffré est m = (m1,. . . , mk).

Homomorphisme

Soit Enc(m1) et Enc(m2)) les chiffrés des messages m1 et m2

Enc(m1) X Enc(m2) = [(r² ₁.z^m1).(r² ₂.z^m2)]_n

= [(r1.r2)².z^m1+m2]_n

= Enc(m1 + m2)

TABLE 2.2 - Comparaison des capacités homomorphes

Cryptosystème	Opérations homo- morphes	problème mathéma- tique		Limites	RSA
X illimité	Factorisation (n = pq)	Aucune addition		ElGamal
X illimité	Logarithme discret (Groupe cyclique)	Pas d'addition		Goldwasser- Micali
+ illimité	Résiduosité quadra- tique	Bits uniquement		Benaloh
+ mod r	Résiduosité	r petit		Paillier
+ mod n^2	Factorisation (n^2)	X non native		BGN
Une X et une + illimité	Appariement bilinéaire	Complexité O(n^2)

Ces cryptosystèmes Pré-FHE présentent des limites fondamentales pour migrer vers le FHE à

savoir:

-- Incomplétude opérationnelle: Aucun ne combine addition et multiplication arbitraires

-- Problème de bruit : Croissance exponentielle dans GM/BGN :

-- Restrictions structurelles : RSA/Paillier dépendent de la factorisation

Ces cryptosystèmes partiellement homomorphes servent de briques théoriques mais nécessitent:

-- Une refonte des primitives cryptographiques

-- L'adoption de modèles de sécurité post-quantique

-- Des optimisations radicales des performances

2.2 Générations du chiffrement homomorphe 24

2.2.2 FHE de première génération

Craig Gentry a réalisé une avancée significative lorsqu'il a présenté en 2009 la première construction plausible d'un chiffrement totalement homomorphe basé sur la cryptographie des réseaux euclidiens. Cette construction développée par Gentry permet de prendre en charge les opérations d'addi-tion et de multiplication sur des textes chiffrés, offrant ainsi la possibilité de créer des circuits pour effectuer des calculs arbitraires. Le processus de construction comprend plusieurs étapes, dans lesquelles du bruit est introduit puis réduit, permettant ainsi d'effectuer un nombre illimité d'additions et de multiplications tout en minimisant l'augmentation du bruit. L'implémentation initiale du cryp-tosystème de Gentry par Gentry-Halevi a nécessité environ 30 minutes par opération simple sur un seul bit. Cependant, des travaux de conception et d'implémentation approfondis réalisés au fil des années ont considérablement amélioré les performances de ces premières implémentations, réduisant le temps d'exécution de plusieurs ordres de grandeur. En 2010, Marten van Dijk, Craig Gentry, Shai Halevi et Vinod Vaikuntanathan [35] ont apporté une contribution majeure en proposant un deuxième cryptosystème de chiffrement entièrement homomorphe basé sur les problèmes SSSP (voir problème 1.1.6)et AGCD( voir problème1.1.7). Leur travail s'appuie sur les avancées réalisées par Gentry, mais présente également de nouvelles techniques et améliorations.

2.2.3 FHE de deuxième génération

Les cryptosystèmes homomorphes utilisés actuellement sont basés sur les techniques développées

en 2011 - 2012 par des chercheurs tels que Zvika Brakerski, Craig Gentry, Vinod Vaikuntanathan, et

d'autres [15]. Ces avancées ont permis le développement de cryptosystèmes beaucoup plus efficace,

offrant des niveaux variables de fonctionnalités homomorphes. Parmi ces avancées, on peut citer:

-- Le cryptosystème de Brakerski-Gentry-Vaikuntanathan, s'appuyant sur les techniques de Brakerski-

Vaikuntanathan;

-- Le cryptosystème basé sur NTRU de Lopez-Alt, Tromer et Vaikuntanathan (LTV);

-- Le cryptosystème Brakerski/Fan-Vercauteren, qui s'appuie sur le cryptosystème invariant d'échelle

de Brakerski;

-- Le cryptosystème basé sur NTRU de Bos, Lauter, Loftus et Naehrig (BLNN), s'appuyant sur

le cryptosystème invariant d'échelle de LTV et Brakerski

2.2.3.1 FHE de trosième génération

En 2013, Craig Gentry, Amit Sahai et Brent Waters (GSW) [33] ont introduit une nouvelle technique pour construire le chiffrement totalement homomorphe qui élimine l'étape coûteuse de "relinéa-risation" dans les opérations homomorphes de multiplication. Cette avancée a été remarquée par Zvika Brakerski et Vinod Vaikuntanathan, qui ont noté que le cryptosystème GSW présente une croissance plus lente du bruit pour certains types de circuits, offrant ainsi une meilleure efficacité et une sécurité renforcée. Jacob Alperin-Sheriff et Chris Peikert ont ensuite proposé une technique de bootstrapping très efficace basée sur cette observation.

Mémoire de Master 2 Recherche 24 MOUYOUME DIEUDONNE(c) UYI

2.2 Générations du chiffrement homomorphe 25

Mémoire de Master 2 Recherche 25 MOUYOUME DIEUDONNE(c) UYI

Ces techniques ont été encore améliorées pour développer des variantes efficaces en anneau du cryptosystème GSW, donnant naissance aux programmes FHEW et TFHE. Le FHEW a introduit une nouvelle méthode pour effectuer des opérations booléennes sur les données chiffrées, simplifiant considérablement le processus de bootstrap et implémentant une variante de la méthode de bootstrapping.

La troisième génération de FHE a réalisé d'importants progrès en termes d'efficacité. Le cryp-tosystème FHEW a réussi à réduire le temps de bootstrapping à une fraction de seconde [16], et le schéma TFHE s'est basé sur ces avancées pour améliorer davantage les performances.

2.2.4 FHE de quatrième génération

C'est dans cette dernière génération qu'on retrouve le cryptosystème CKKS (Cheon-Kim-Kim-Song) qui réalise des opérations avec des calculs arrondis. Cela a pour effet de limiter le bruit inhérent aux opérations de multiplication, et ainsi de réduire le nombre de réamorçages (bootstrapping) nécessaires dans un circuit. Une caractéristique importante du cryptosystème CKKS est qu'il code les valeurs estimées plutôt que les valeurs exactes, ce qui le rend particulièrement adapté aux applications d'apprentissage automatique chiffré.

TABLE 2.3 - Tableau récapitulatif des cryptosystèmes FHE

Type de cryptosystème		Année	Gentry (proposé par Craig Gentry dans sa thèse de doctorat)
2009		DGHV (Marten van Dijk, Craig Gentry, Shai Halevi, and Vinod Vaikuntanathan)
2010		BGV (Brakerski-Gentry-Vaikuntanathan)
2011		BFV (Brakerski/Fan-Vercauteren)
2012		BLLN (Bos, Lauter, Loftus, and Naehrig)
2013		GSW (Craig Gentry, Amit Sahai, and Brent Waters)
2013		CKKS (Cheon-Kim-Kim-Song)
2016

2.2.5 Cryptosystèmes basés sur le problème Ring-LWE

2.2.5.1 Cryptosystème de Brakerski, Gentry et Vaikuntanathan

Le cryptosystème BGV a été inventé en 2011 par Brakerski, Gentry et Vaikuntanathan [2][6]. BGV est un FHE nivelé, c'est-à-dire que les paramètres du schéma dépendent (polynomialement) du nombre maximum de multiplications pouvant être exécutées (appelé niveau l).

Les espaces des textes en clairs et des textes chiffrés

Les espaces des textes en clairs et des textes chiffrés sont définis sur deux anneaux polynomiaux distincts désignés par:

-- R_p = 1_p[X]/(X^d + 1) d = 2^k, k > 2 et p le module du texte en clair

-- Rql × Rql oÙ Rql = 1_ql[X]/(X^d + 1) avec d = 2^k, k > 2 et ql le module des chiffrés au niveau l.

2.2 Générations du chiffrement homomorphe 26

Mémoire de Master 2 Recherche 26 MOUYOUME DIEUDONNE(c) UYI

Ainsi les fonctions de BGV sont :

Génération des clés

La clé secrète est sk un polynôme de degré n avec les coefficients dans {-1, 0, 1) échantillion-nées suivant une loi uniforme (voir la définition 1.1.12). La clé publique pk est une paire de polynômes (pk1, pk2) calculée comme suit : pk1 = [-(a.s + p.e)]ql et pk2 = a

Avec a est un polynôme aléatoire, les coefficients de a sont générés avec une distribution uniforme (voir définition 1.1.12) dans {1^-ql₂ 1, ... , L^ql₂ J) et e est un polynôme d'erreur aléatoire dont les coefficients sont échantillonnés à partir distribution gaussienne discrète x(voir définition 1.1.11).

Chiffrement

Un texte clair m est chiffré par c = (c1, c2) avec : c1 = [pk1.v + p.e1 + m]ql, c2 = [pk2.v + p.e2]ql)

Avec v est un polynôme de degré n généré avec des coefficients aléatoires dans {-1,0,1} suivant une loi uniforme (voir définition 1.1.12), e1 et e2 sont des polynômes de degré n suivants x, la distribution d'erreur définie comme une distribution gaussienne discrète (voir définition1.1.11).

Déchiffrement

Un texte chiffré au niveau l est déchiffré en calculant :

m = [[c1 + c2.sk]ql]p

Evaluation homomorphique

L'addition de deux textes chiffrés c1 = (c11, c12) et c2 = (c21, c22) au même niveau l est calculé par

EvalAdd(c1, c2) = ([c11 + c12]ql, [c21, c22]ql)

La multiplication de deux textes chiffrés c1 = (c11, c12) et c2 = (c21, c22) renvoie le résultat

EvalMult(c1, c2) = ([c11.c21]ql, [c11.c22 + c12.c21]ql, [c12.c22]ql)

qui est un chiffré qui n'est plus sous forme initiale c = (c1, c2) mais sous forme étendue (àc1, àc2, àc3). Le processus de relinéarisation permet de le réduire le chiffré (àc1, àc2, àc3) en un chiffré de la forme (c1, c2) oú :

c1 = [àc1 + EK1.àc3]ql

c2 = [àc2 + EK1.àc3]ql

Avec EK = (-(a.sk + e) + sk², a)

2.2 Générations du chiffrement homomorphe 27

Mémoire de Master 2 Recherche 27 MOUYOUME DIEUDONNE(c) UYI

Le SwitchModulus ou réduction du module est utilisé pour contrôler le bruit de la multiplication. Le texte chiffré transformé c^' est défini par rapport au nouveau module q^' < q. On a c^' = [^q'_q .c]

2.2.5.2 Cryptosystème de Brakerski, Fan et Vercauteren

Le cryptosystème BFV a été proposé en 2012 par J. Fan et F. Vercauteren [28] après avoir modifié le schéma proposé par Brakerski [15]. Le cryptosystème BFV est similaire au cryptosystème BGV mais ayant ses spécificités.

Les espaces de texte en clair et de texte chiffré

Les espaces de texte en clair et de texte chiffré sont définis sur deux anneaux polynomiaux distincts désignés par :

R_p = 7L_p[X]/(X^d + 1) d = 2^k, k = 2 et p le module du texte en clair

R_q × R_q où R_q = 7L_q[X]/(X^d + 1) avec d = 2^k, k = 2 et q le module du texte chiffré . Ainsi les fonctions de BFV [14] sont :

Génération des clés

La clé secrète est sk un polynôme de degré n avec les coefficients dans {-1, 0, 1} échantillion-nées suivant une loi uniforme (voir la définition 1.1.12).. La clé publique pk est une paire de polynômes (pk1, pk2) calculée comme suit : pk1 = [-(a.s + e)]q et pk2 = a

Avec a un polynôme aléatoire, les coefficients de a sont générés avec une distribution uniforme (voir définition 1.1.12) dans {?-q ₂ ?,..., ?^q₂?} et e est un polynôme d'erreur aléatoire dont les coefficients sont échantillonnés à partir d'une distribution gaussienne discrète de x (voir définition 1.1.11).

Chiffrement

Un texte clair m est chiffré par c = (c1, c2) avec : c1 = [pk1.u + e1 + ?m]q, avec ? = ?^q p? c2 = [pk2.u + e2]q

Avec u un polynôme de degré n généré avec des coefficients aléatoires dans {-1,0,1} suivant une loi uniforme (voir la définition 1.1.12), e1 et e2 sont des polynômes de degré n suivantx, la distribution d'erreur définie comme une distribution gaussienne discrète x (voir la définition 1.1.11).

Déchiffrement

Un texte chiffré m est déchiffré en calculant : m = [?p.[c1+c2.sk]q?] q q.

Evaluation homomorphique

L'addition de deux textes chiffrés c1 = (c11, c12) et c2 = (c21, c22) est caclculé par :

2.2 Générations du chiffrement homomorphe 28

Mémoire de Master 2 Recherche 28 MOUYOUME DIEUDONNE(c) UYI

-- EvalAdd(c1, c2) = ([c11 + c12]q, [c21, c22]q).

La multiplication de deux textes chiffrés c1 = (c11, c12) et c2 = (c21, c22) renvoie le resultat : -- EvalMult(c1, c2) = ([L p(c11.c21)

_q l]_q), [L p(c11.c22+c12.c21)

_q l]_q, [L p(c12.c22)

_q l]q)

qui est un chiffré qui n'est plus sous forme initiale c = (c1, c2) mais sous forme étendue (àc1, àc2, àc3). Le processus de rélinéarisation permet de le réduire le chiffré àc1, àc2, àc3) en un chiffré de la forme (c1,c2) oû :

c1 = [àc1 + EK1.àc3]q

c2 = [àc2 + EK2.àc3]q

Avec EK = (-(a.sk + e) + sk², a) 2.2.5.3 Cryptosystème CKKS

Le cryptosystème CKKS(Cheon-Kim-Kim-Song) a été proposé par Cheon et al. [18]. Contrairement aux autres systèmes de chiffrement homomorphe , le système CKKS prend en charge l'arithmé-tique approximative sur les nombres complexes.

Espace du texte en clair et l'espace du texte chiffré

CKKS exploite la riche structure des anneaux de polynômes entiers pour ses espaces du texte en clair et du texte chiffré. Néanmoins, les données se présentent plus souvent sous la forme de vecteurs que de polynômes. Par conséquent, il est nécessaire d'encoder notre entrée z E C^d/² en un polynôme m(X) E Z[X]/(X^d + 1) où d est une puissance de 2.

L'espace de texte en clair est l'anneau polynomial R = Z[X]/(X^d + 1).

L'espace du texte chiffré est (Z[X]/(X^d + 1))² où q est le module des chiffrés.

Le système CKKS se compose essentiellement des algorithmes suivants : génération de clés, chiffrement, déchiffrement, addition et multiplication homomorphes et remise à l'échelle.

Génération des clés

La clé secrète est sk un polynôme de degré n avec les coefficients dans {-1,0, 1) échantillion- nées suivant une loi uniforme (voir la définition 1.1.12). La clé publique pk est une paire de polynômes pk1 et pk2 calculée comme suit: -- pk1 = [-a.s + e]q et -- pk2 = a

Avec, a est un polynôme aléatoire échantillonné uniformément à partir de R_q, et e est un polynôme d'erreur aléatoire échantillonné à partir de ÷.

2.2 Générations du chiffrement homomorphe 29

Chiffrement

Un message clair m ? R est chiffré par c = (c1, c2) ? R^2q avec : c1 = r.pk1 + e1 + m c2 = r.pk2 + e2

Mémoire de Master 2 Recherche 29 MOUYOUME DIEUDONNE(c) UYI

Avec r un polynôme de degré n généré avec des coefficients aléatoires dans {-1,0,1} suivant une loi uniforme (voir la définition 1.1.12), e1 et e2 sont des polynômes de degré n dans les coefficients suivent la distribution d'erreur définie comme une distribution gaussienne discrète ÷ (voir la définition 1.1.11).

Déchiffrement

Un texte chiffré m est déchiffré en calculant :

m = [c1 + c2.sk]_q

Evaluation homomorphique

L'addition de deux textes chiffrés c1 = (c11, c12) et c2 = (c21, c22) est caclculé par :

EvalAdd(c1, c2) = ([c11 + c12]q, [c21, c22]q).

La multiplication de deux textes chiffrés c1 = (c11, c12) et c2 = (c21, c22) renvoie le resultat :

EvalMult(c1, c2) = ([(c11.c21)]q), [(c11.c22 + c12.c21)]q, [(c12.c22)]q)

qui est un chiffré qui n'est plus sous forme initiale c = (c1, c2) mais sous forme étendue (àc1, àc2, àc3). Le processus de rélinéarisation permet de le réduire le chiffré (àc1, àc2, àc3) en un chiffré de la forme (c1, c2) où :

c1 = àc1 + ?p^-1.àc3.EK1?

c2 = àc2 + ?p^-1.àc3.EK2?

Avec EK = (EK1, EK2) = (-a^'.sk + e^') + p.sk², a'); a^' est éhantillonné uniformément au hasard à partir de _Rpq et e^' une erreur suivant la distribution gaussienne discète ÷.

2.2.6 Quelques applications du FHE

Le FHE ouvre la voie à de nombreuses applications dans divers domaines [53], notamment :

Le vote électronique

Le vote électronique traditionnel nécessite de décrypter les votes pour les additionner, créant un risque de fraude lors du dépouillement. En revanche, un système utilisant le chiffrement ho-momorphe permet d'additionner les votes directement sous forme chiffrée, sans déchiffrement intermédiaire, ce qui renforce la sécurité.

Calcul sécurisé dans le cloud

2.2 Générations du chiffrement homomorphe 30

Mémoire de Master 2 Recherche 30 MOUYOUME DIEUDONNE(c) UYI

Les entreprises peuvent utiliser le FHE pour traiter des données sensibles dans le cloud sans compromettre leur confidentialité. Par exemple, des calculs complexes sur des données médicales peuvent être effectués de manière sécurisée sans révéler les informations personnelles des patients.

-- Protection de la vie privée

Les utilisateurs individuels peuvent bénéficier du FHE pour protéger leur vie privée en ligne. Par exemple, les applications de messagerie peuvent utiliser le FHE pour chiffrer les conversations de bout en bout, garantissant ainsi que même le fournisseur de services ne peut pas accéder aux messages des utilisateurs.

-- Analyse de données sécurisées

Les chercheurs et les analystes de données peuvent utiliser le FHE pour effectuer des analyses sur des ensembles de données sensibles tout en préservant la confidentialité des données. Par exemple, des études sur les données médicales ou financières peuvent être menées de manière sécurisée sans compromettre la vie privée des individus concernés.

-- IA et Machine Learning

Selon IBM, le chiffrement totalement homomorphe est de plus en plus compatible avec le machine learning et les réseaux de neurones.

-- Chiffrement des données biométriques et analyse des comportements

Il s'agit de protéger les données biométriques et les cas d'usage d'analyse comportementale côté serveur.

-- Analyses prédictives chiffrées dans les services financiers

Bien que le ML permette de créer des modèles prédictifs pour des activités comme la lutte contre la fraude, les transactions financières et les rendements d'investissements, les réglementations et les politiques empêchent souvent les organisations de partager et d'exploiter les données sensibles. Le FHE permet le calcul de données chiffrées à l'aide de modèles de ML sans exposer les informations.

-- Confidentialité dans le secteur de la santé et des sciences de la vie

Malgré l'efficacité du cloud dans l'hébergement des workloads pour les essais cliniques de grande ampleur, les risques liés à la confidentialité et les réglementations sanitaires empêchent souvent les hôpitaux de passer au cloud. Le FHE peut améliorer l'acceptation des protocoles de partage des données, augmenter la taille des échantillons dans la recherche clinique et accélérer l'apprentissage à partir de données réelles.

-- Recherche chiffrée dans le secteur du commerce et des services aux consommateurs La technologie permet de surveiller à grande échelle la manière dont les consommateurs recherchent et accèdent aux informations, mais il est difficile pour les organisations de monétiser ces données en raison des droits de protection de la vie privée. Le FHE permet d'obtenir des informations sur le comportement des consommateurs tout en masquant les requêtes des utilisateurs et en protégeant le droit des individus à la vie privée.

2.2 Générations du chiffrement homomorphe 31

Mémoire de Master 2 Recherche 31 MOUYOUME DIEUDONNE(c) UYI

2.2.7 Avantages du FHE

Le chiffrement homomorphe est très important car il permet d'effectuer des calculs sur des données chiffrées. Cela signifie que le traitement des données peut être confié à un tiers sans qu'il soit nécessaire de lui faire confiance pour sécuriser correctement les données. Sans la clé de déchiffrement appropriée, il est impossible d'accéder aux données d'origine.Ainsi le FHE présente plusieurs avantages [39] parmi lesquels on peut citer:

-- Le renforcement la sécurité et la confidentialité des traitements effectués par des tiers. En général, le traitement des renseignements personnels par des tiers se fait sur des données non chiffrées, en clair. Cela soulève plusieurs risques pour la vie privée et la sécurité des personnes. Cependant, le chiffrement homomorphe peut aider à se prémunir contre ces risques en garantissant que toutes les données restent chiffrées tout au long de leur cycle de vie de traitement, que ce soit dans le nuage ou sur une chaîne de blocs.

-- La préservation de l'exactitude des données

Le processus de chiffrement des renseignements personnels ne modifie pas la signification sous-jacente ou la structure interne de l'information. Ses valeurs et les relations qu'elle entretient restent les mêmes. Ce qui change avec le chiffrement, c'est uniquement l'aspect extérieur et la confidentialité. Il empêche l'accès à l'information et la dissimule.

-- La résistances des algorithmes actuels aux attaques quantiques

L'informatique quantique est un domaine de recherche multidisciplinaire émergent qui cherche à exploiter les propriétés contre-intuitives de la mécanique quantique pour concevoir et exécuter des algorithmes capables de résoudre certains problèmes plus rapidement que les ordinateurs classiques.

-- Informations précieuses

Générez des avantages économiques mesurables en permettant aux branches d'activité et aux tiers d'effectuer des analyses big data sur des données chiffrées tout en maintenant les contrôles de confidentialité et de conformité.

-- Collaborer en toute confiance sur le cloud hybride

Traitez des données chiffrées dans des cloud publics et privés et dans des environnements tiers tout en maintenant des contrôles de confidentialité.

-- Exploiter l'IA, l'analytique et le machine learning (ML)

Utilisez l'IA et le ML pour effectuer des calculs sur des données chiffrées sans exposer d'in-formations sensibles.

2.2.8 Limites des techniques actuelles de chiffrement homomorphe

Les techniques actuelles de chiffrement homomorphe sont confrontées à plusieurs défis qui im-pactent leur application pratique [39][51] à l'instar de :

-- La surcharge de calcul constitue une limitation importante.

La surcharge de calcul constitue une limitation importante. L'exécution d'opérations com-

2.2 Générations du chiffrement homomorphe 32

Mémoire de Master 2 Recherche 32 MOUYOUME DIEUDONNE(c) UYI

plexes sur des données chiffrées requiert une puissance de traitement importante, ce qui ralentit les vitesses d'exécution par rapport aux calculs traditionnels non chiffrés. Cette charge de calcul peut constituer un obstacle, notamment pour les applications temps réel où la réactivité est essentielle. Cette charge, particulièrement importante pour le chiffrement entièrement homomorphe, peut rendre la mise en oeuvre coûteuse , limitant potentiellement son adoption par les grandes organisations disposant de ressources importantes. La puissance de traitement et la mémoire nécessaires aux calculs sécurisés sur des données chiffrées peuvent grever les budgets.

-- Les types de calculs pris en charge.

Une autre limitation réside dans les types de calculs pris en charge. La plupart des schémas de chiffrement homomorphe existants sont soit partiellement homomorphes (prenant en charge des opérations spécifiques comme l'addition ou la multiplication), soit totalement ho-momorphes, mais avec des limitations quant à la profondeur des calculs. Les techniques de chiffrement totalement homomorphes sont généralement plus gourmandes en ressources, ce qui limite leur faisabilité dans les environnements aux ressources limitées.

-- La gestion des clés

La gestion des clés pose un défi. Générer, distribuer et gérer des clés de chiffrement de manière sécurisée, en particulier dans les applications à grande échelle, exige des protocoles et une infrastructure robustes.

-- La taille des données pouvant être traitées

De plus, des considérations pratiques s'appliquent concernant la taille des données pouvant être traitées. Le chiffrement homomorphe gonfle la taille des données chiffrées , les rendant nettement plus volumineuses que les données d'origine. La transmission et le stockage de ces ensembles de données étendus peuvent solliciter la bande passante du réseau et les ressources de stockage.

La prise en compte de ces limites est essentielle à l'adoption généralisée du chiffrement homo-morphe. Fort de ces limites, le domaine du chiffrement homomorphe continue d'évoluer, se rapprochant progressivement de son plein potentiel pour remodeler le paysage du traitement sécurisé des données.

Mémoire de Master 2 Recherche 33 MOUYOUME DIEUDONNE(c) UYI

Chapitre III

SYSTEMES DE CALCULS HOMOMORPHES

Ce chapitre porte sur l'étude de quelques bibliothèques Open-source FHE

3.1 Bibliothèques logicielles

Le Robert dico en ligne définit une bibliothèque comme une salle, édifice où sont classés des livres, pour la lecture ou pour le prêt.

Une bibliothèque comprend toute collection organisée de livres et de publications périodiques sous forme imprimée ou électronique ou tout autre matériel graphique ou audiovisuel (d'après l'UNESCO, 1970). En informatique, une bibliothèque logicielle [52] [20] est une collection de routines, qui peuvent être déjà compilées et prêtes à être utilisées par des programmes. Les bibliothèques sont enregistrées dans des fichiers semblables, voire identiques aux fichiers de programmes, sous la forme d'une collection de fichiers de code objet rassemblés accompagnée d'un index permettant de retrouver facilement chaque routine.

Les bibliothèques sont apparues dans les années 1950, et sont devenues un sujet incontournable de programmation. Elles sont utilisées pour réaliser des interfaces de programmation, des frameworks, des plugins ainsi que des langages de programmation. Les routines (En informatique, une routine est un ensemble d'instructions qui prend en charge une certaine opération et produit un résultat) contenues dans les bibliothèques sont typiquement en rapport avec des opérations fréquentes en programmation: manipulation des interfaces utilisateur, manipulation des bases de données ou calculs mathématiques.

Les bibliothèques sont manipulées par l'éditeur de lien et le système d'exploitation. Les manipulations sont différentes selon que la bibliothèque est statique ou partagée. Les emplacements et les noms des bibliothèques varient selon les systèmes d'exploitation.

Les bibliothèques sont utilisées pour mettre en oeuvre des interfaces de programmation ainsi que des frameworks et des plugins et peuvent être incorporées dans les langages de programmation.

3.1.1 Conception et organisation des bibliothèques

L'organisation classique des bibliothèques passe par un découpage thématique des fonctions, permettant au programmeur de retrouver plus facilement la fonction dont il a besoin. Ce découpage thématique permet de classer les bibliothèques selon les services qu'elles rendent:

·

3.2 Bibliothèques FHE 34

Mémoire de Master 2 Recherche 34 MOUYOUME DIEUDONNE(c) UYI

Bibliothèques de bas niveau ou bibliothèques système : elles fournissent des services d'in-terface avec le système d'exploitation, avec les périphériques, ou fournissent des outils génériques:

-- bibliothèques d'entrées/sorties : fonctions de lecture et d'écriture de fichiers, de périphériques d'entrée/sortie comme le clavier, l'écran, etc.

-- gestion de structures de données système,

· Bibliothèques de haut niveau (aussi appelées bibliothèques métier, elles interagissent avec celles de bas niveau) : les fonctions qu'elles contiennent sont propres à une activité spécifique: -- boîtes à outils graphiques : ensemble de fonctions permettant de gérer, d'animer et d'af-ficher des objets graphiques complexes.

-- bibliothèques d'opérateurs de traitement d'image : ensemble de fonctions destinées à structurer l'information dans une image à des fins d'analyse.

· Autres bibliothèques:

-- combinateurs en programmation fonctionnelle,

-- protocoles de métaprogrammation.

combinateurs en programmation fonctionnelle, protocoles de métaprogrammation.

3.1.2 Principes

Pour que le code exécutable puisse accéder aux instructions d'une fonction d'une bibliothèque qu'il utilise, il faut que chaque appel de fonction dans le code soit associé à l'adresse effective de la première instruction de la fonction appelée dans la bibliothèque. Pour cela, il existe plusieurs méthodes et outils, qui interviennent après l'étape de compilation:

-- l'édition de liens assure la mise en place, dans le code exécutable de l'application, des instructions de branchement vers les fonctions externes (issues d'une ou de plusieurs bibliothèques);

-- si l'édition de lien est dynamique, intervient un chargeur permettant, lors de l'exécution du programme, d'amener en mémoire les fonctions des bibliothèques utilisées, de sorte que lors-qu'une fonction est appelée, son code soit disponible en mémoire.

-- si l'édition est statique, le code des fonctions utilisées par l'application est intégré au code de l'application qui devient par là-même autonome.

Le chargement des bibliothèques peut survenir de deux manières:

-- À la volée, lors d'un appel par le programme qui en exploite une fonction (liaison tardive), cette technique a l'avantage de ne charger que le code réellement nécessaire,

-- Ou au chargement du programme en vue de son exécution.

3.2 Bibliothèques FHE

Une bibliothèque FHE est une bibliothèque logicielle permettant d'effectuer des calculs sur des données chiffrées de manière homomorphique et sécurisée. Le concept clé derrière les bibliothèques homomorphiques est d'effectuer des opérations sur des données chiffrées, sans avoir besoin de les

3.2 Bibliothèques FHE 35

Mémoire de Master 2 Recherche 35 MOUYOUME DIEUDONNE(c) UYI

3.2 Bibliothèques FHE 36

déchiffrer. Cela signifie que les calculs peuvent être effectués sur des données sensibles tout en les maintenant confidentielles. Les bibliothèques FHE utilisent des techniques de chiffrement spécifiques, telles que le chiffrement entièrement homomorphe (FHE), le chiffrement quelque peu homomorphe (SWHE) ou le chiffrement partiellement homomorphe (PHE), pour permettre ces calculs sur les données chiffrées.

Ces bibliothèques fournissent généralement une interface de programmation (API) qui permet aux développeurs d'utiliser les fonctionnalités de calcul homomorphique dans leurs applications. Elles peuvent prendre en charge diverses opérations homomorphes, telles que l'addition, la multiplication, les opérations logiques, etc., selon les capacités du cryptosystème de chiffrement sous-jacent. Ils existent plusieurs bibliothèques FHE qui sont Open source parmi lesquels:

3.2.1 HElib

HElib est une bibliothèque logicielle open-source (Apache License v2.0) qui implémente le chiffrement homomorphe (HE). Les schémas actuellement disponibles sont les implémentations du cryp-tosystème Brakerski-Gentry-Vaikuntanathan (BGV) avec bootstrap et le schéma du nombre approximatif de Cheon-Kim-Kim-Song (CKKS), ainsi que de nombreuses optimisations pour accélérer l'éva-luation homomorphique, en se concentrant principalement sur utilisation efficace des techniques d'emballage de texte chiffré Smart-Vercauteren et des optimisations Gentry-Halevi-Smart. HElib est écrit en C++17 et utilise la bibliothèque mathématique NTL.

Depuis la mi-2018, HElib a fait l'objet d'une refactorisation approfondie pour la fiabilité, la robustesse et la facilité d'entretien, les performances et, surtout, la convivialité pour les chercheurs et les développeurs travaillant sur HE et ses utilisations.

HElib prend en charge un "langage d'assemblage pour HE", fournissant des routines de bas niveau (définir, ajouter, multiplier, décaler, etc.), une gestion automatique sophistiquée du bruit, un démarrage BGV amélioré, le multi-threading et également la prise en charge des objets Ptxt (texte clair) qui imite la fonctionnalité des objets Ctxt (texte chiffré).

3.2.2 HEAAN

HEAAN(Homomorphic Encryption for Arithmetic of Approximate Numbers)[53] est une bibliothèque C++ qui utilise la librairie NTL(Number Theory Library) et facilite le chiffrement, le déchiffrement et la génération de clés homomorphes, ainsi que les évaluations homomorphes fondamentales telles que l'addition, la multiplication et la rotation. Débutant par une implémentation de référence du cryptosystème CKKS, HEAAN a évolué afin d'améliorer ses performances et d'incorporer les résultats de recherche les plus récents dans la bibliothèque. Du point de vue des performances, HEAAN prend en charge une implémentation exquise du CPU, en utilisant de nombreuses avancées technologiques des CPU telles que Intel(R) AVX2/AVX512. HEAAN fournit également une version de la bibliothèque accélérée par le GPU. Ce programme est sous licence Creative Commons Attribution-NonCommercial 3.0 et est la propriété CryptoLab inc.

Mémoire de Master 2 Recherche 36 MOUYOUME DIEUDONNE(c) UYI

3.2.3 Lattigo

Lattigo [1] est un module Go qui implémente des primitives de chiffrement homomorphe basées sur Ring-Learning With Errors et des protocoles sécurisés basés sur Multiparty Homomorphic Encryption. La bibliothèque propose:

-- Une implémentation des systèmes RNS (Residue Number System) complets BFV, BGV et CKKS et leurs versions multipartites respectives.

-- Performances comparables aux bibliothèques C++ de pointe.

-- Procédures d'amorçage efficaces et de haute précision à clés denses et à clés creuses pour les CKKS à RNS complet.

3.2.4 ?oA(Lol)

?oA(Lol) [22] est une bibliothèque polyvalente pour la cryptographie en treillis en anneau. Le framework ?oA présente plusieurs propriétés innovantes qui le distinguent des implémentations précédentes de cryptosystèmes en treillis, notamment:

-- Généralité, modularité, concision: ?oA définit un ensemble d'interfaces générales et hautement composables pour les opérations mathématiques utilisées en cryptographie en treillis, permettant d'exprimer une grande variété de schémas de manière très naturelle et avec un haut niveau d'abstraction. Par exemple, nous implémentons un schéma avancé de chiffrement entièrement homomorphe (FHE) en seulement 2 à 5 lignes de code par fonctionnalité, grâce à un code qui correspond étroitement à la définition mathématique du schéma.

-- Affinité théorique :?oA est conçu dès le départ autour des représentations d'anneaux spécialisées, des algorithmes rapides et des preuves de dureté du pire cas développés pour le problème Ring-LWE et ses applications cryptographiques. Il implémente notamment des algorithmes rapides d'échantillonnage à partir de distributions d'erreurs théoriquement recommandées sur des anneaux cyclotomiques arbitraires, et fournit des outils permettant de contrôler étroitement la croissance des erreurs dans les schémas cryptographiques.

-- Sécurité : ?oA dispose de plusieurs fonctionnalités permettant de réduire la complexité du code et les erreurs de programmation, facilitant ainsi l'implémentation correcte des cryptosys-tèmes en treillis. Il utilise notamment un typage fort pour appliquer statiquement, c'est-à-dire à la compilation, une grande variété de contraintes entre les différents paramètres.

-- Fonctionnalités avancées :?oA expose la riche hiérarchie des anneaux cyclotomiques aux applications cryptographiques.

3.2.5 FHEW

FHEW [25]est un logiciel open-source distribué sous les termes de la Licence Publique Générale GNU (GPL) Apache 2.0. Bien que son code soit principalement en C, des extensions C++ (espaces de noms, paramètres par référence) sont utilisées pour améliorer la lisibilité. Elle est testé avec g++

3.2 Bibliothèques FHE 37

Mémoire de Master 2 Recherche 37 MOUYOUME DIEUDONNE(c) UYI

(GCC 4.9.1), mais fonctionne avec d'autres compilateurs. Une adaptation pour un compilateur C pur est possible via des modifications mineures.

Elle es basé sur le schéma de chiffrement homomorphe FHEW et elle utilise la bibliothèque FFTW (Fastest Fourier Transform in the West).

Ses fonctionnalités clés sont:

-- Chiffrement symétrique de messages binaires (1 bit).

-- Évaluation homomorphe de circuits booléens arbitraires via une clé publique d'évaluation. Elle nécessite l'installation de FFTW 3 Compilateur C++ : Bien que le code soit principalement en C, des extensions C++ (espaces de noms, paramètres par référence) sont utilisées pour améliorer la lisibilité. Compatibilité: Testé avec g++ (GCC 4.9.1), mais fonctionne avec d'autres compilateurs. Une adaptation pour un compilateur C pur est possible via des modifications mineures.

Sa version 2.0-alpha (bêta) -- Date de sortie: 30 mai 2017 a des mises à jour suivantes:

-- Accélération x6 des calculs de portes homomorphes

-- Optimisation via la reconnaissance qu'il suffit de calculer ACC. Cette astuce équivaut concep-

tuellement au « produit externe » décrit dans ce papier académique.

-- Prise en charge de nouvelles portes logiques : AND, OR, NAND, NOR, NOT. Interdiction des

opérations sur des chiffrements non indépendants : ex. (x OP x) ou (x OP (non x)).

-- Corrections de bugs.

3.2.6 NFLlib

NFLlib [23] est une bibliothèque C++ performante et open source dédiée à la cryptographie sur réseau idéal. Elle est spécialisée dans les anneaux de polynômes quotientés par un polynôme cyclo-tomique de degré puissance deux.

La bibliothèque combine des optimisations algorithmiques (théorème des restes chinois, transformée de la théorie des nombres optimisée) et des techniques d'optimisation de programmation (spécialisations SSE et AVX2, modèles d'expressions C++, etc.).

Elle est sous licence MIT et nécéssite le cmake, GMP et Mpfr, ainsi que d'un compilateur C++11.

3.2.7 cuHE

La bibliothèque de chiffrement homomorphe CUDA (cuHE) [31] est une bibliothèque accélérée par GPU pour les schémas et algorithmes de chiffrement homomorphe (HE) définis sur des anneaux polynomiaux. cuHE offre des performances exceptionnelles tout en offrant une interface simple qui améliore considérablement la productivité des programmeurs. Elle intègre des techniques algébriques pour l'évaluation homomorphe des circuits et un code hautement optimisé pour les machines mono-GPU ou multi-GPU.

La bibliothèque cuHE est distribuée sous licence MIT (MIT). Elle est actuellement destinée à la recherche uniquement. Plusieurs algorithmes sont implémentés à titre d'exemple et d'autres suivront.

3.2 Bibliothèques FHE 38

Mémoire de Master 2 Recherche 38 MOUYOUME DIEUDONNE(c) UYI

La bibliothèque repousse les limites des performances. Plusieurs optimisations, telles que des techniques algébriques pour une évaluation efficace, des techniques de minimisation de la mémoire, l'ordonnancement de la mémoire et des flux, ainsi que des optimisations d'assemblage CUDA de bas niveau, sont incluses pour tirer pleinement parti du parallélisme massif et de la bande passante mémoire élevée des GPU. Les fonctions arithmétiques conçues pour gérer de très grands opérandes polynomiaux adoptent le théorème des restes chinois (CRT), la transformée de la théorie des nombres (NTT) et les méthodes basées sur la réduction de Barrett.

Les configurations requises sont:

-- GPU NVIDIA CUDA avec compatibilité de calcul 3.0 ou supérieure

-- NTL : Bibliothèque pour la théorie des nombres 9.3.0 (nécessite C++11).

-- API OpenMP

3.2.8 TFHE

TFHE [19] est une bibliothèque open source pour le chiffrement entièrement homomorphe, distribuée sous licence Apache 2.0. Le schéma sous-jacent est le TFHE

TFHE est une bibliothèque C/C++ qui implémente un amorçage porte par porte très rapide, basé sur et . Cette bibliothèque permet d'évaluer un circuit booléen arbitraire composé de portes binaires, sur des données chiffrées, sans révéler aucune information sur les données.

La bibliothèque prend en charge l'évaluation homomorphe des 10 portes binaires (And, Or, Xor, Nand, Nor, etc.), ainsi que la négation et la porte Mux. Chaque porte binaire prend environ 13ms en temps monocoeur pour être évaluée, ce qui améliore d'un facteur 53, et la porte Mux prend environ 26ms CPU.

Contrairement à d'autres bibliothèques, le mode d'amorçage de portes de TFHE n'impose aucune restriction quant au nombre de portes ni à leur composition. Cela permet d'effectuer n'importe quel calcul sur des données chiffrées, même si la fonction appliquée n'est pas encore connue au moment du chiffrement. La bibliothèque est facile à utiliser, que ce soit avec des circuits créés manuellement ou avec les résultats d'outils de génération de circuits automatisés.

Du point de vue de l'utilisateur, la bibliothèque peut:

-- Générer un jeu de clés secrètes et un jeu de clés cloud. Le jeu de clés secrètes est privé et offre des capacités de chiffrement/déchiffrement. Le jeu de clés cloud peut être exporté vers le cloud et permet d'opérer sur des données chiffrées.

-- Grâce au jeu de clés secrètes, la bibliothèque permet de chiffrer et de déchiffrer des données. Les données chiffrées peuvent être externalisées vers le cloud en toute sécurité afin d'effectuer des calculs homomorphes sécurisés.

-- Grâce au jeu de clés cloud, la bibliothèque peut évaluer une liste de portes binaires de manière homomorphe à une cadence d'environ 76 portes par seconde et par coeur, sans déchiffrer ses entrées. Il suffit de fournir la séquence de portes, ainsi que les textes chiffrés des bits d'entrée. La bibliothèque calcule ensuite les textes chiffrés des bits de sortie.

3.2 Bibliothèques FHE 39

Mémoire de Master 2 Recherche 39 MOUYOUME DIEUDONNE(c) UYI

3.2.9 pyFHE

pyFHE [27] est une bibliothèque Python 3 pour le chiffrement entièrement homomorphe. Cette bibliothèque inclut actuellement une implémentation des schémas Brakerski-Fan-Vercauteren (BFV), Cheon-Kim-Kim-Song (CKKS) et l'amorçage pour CKKS.

pyFHE est conçu pour disposer d'un ensemble commun de classes pour chaque schéma de chiffrement entièrement homomorphe. Les couches sont organisées comme suit:

-- 1. Schéma de chiffrement : Les schémas existants dans pyFHE sont BFV et CKKS.

-- 12. Méthodes de chiffrement : Elles incluent tous les protocoles cryptographiques d'un schéma.

3. Objets cryptographiques : Ces objets sont communs à tous les schémas cryptographiques.

4. Couche Anneau polynomial : Elle permet d'effectuer des opérations telles que l'addition et la multiplication dans l'anneau Z[x]/(xⁿ + 1).

5. Couche Mathématiques et FFT : Elle inclut toutes les opérations mathématiques et de théorie des nombres de base, y compris la FFT, la NTT, la CRT et l'échantillonnage aléatoire.

3.2.10 TenSEAL

TenSEAL [10] est une bibliothèque permettant d'effectuer des opérations de chiffrement homo-

morphique sur des tenseurs, construite au-dessus de Microsoft SEAL. Elle offre une facilité d'uti-

lisation grâce à une API Python, tout en préservant l'efficacité en implémentant la plupart de ses

opérations en C++. Elle permet de :

-- Chiffrement/déchiffrement de vecteurs d'entiers à l'aide de BFV

-- Chiffrement/déchiffrement de vecteurs de nombres réels à l'aide de CKKS

Les plates formes prises en charge et leurs exigences:

-- Linux: Une version moderne de GNU G++ (>= 6.0) ou Clang++ (>= 5.0).

-- MacOS : Xcode toolchain (>= 9.3)

-- Windows : Microsoft Visual Studio (>= 10.0.40219.1, Visual Studio 2010 SP1 ou plus ré-

cent).

3.2.11 Concrete

Concrete [54] est un compilateur FHE open source qui simplifie l'utilisation du chiffrement entièrement homomorphe (FHE). Basé sur la technologie TFHE et exploitant LLVM, Concrete rend l'écriture de programmes FHE accessible aux développeurs sans expertise approfondie en cryptographie.

Les configurations requises sont:

-- Python 3.9 - 3.12

-- 8 Go de RAM minimum (16 Go recommandés)

-- Processeur x86_64 ou ARM64

3.2 Bibliothèques FHE 40

Mémoire de Master 2 Recherche 40 MOUYOUME DIEUDONNE(c) UYI

3.2.12 Microsoft SEAL

Microsoft SEAL [38][47] est une bibliothèque de chiffrement homomorphe open source (sous licence MIT) facile à utiliser développée par le groupe de recherche sur la cryptographie et la confidentialité de Microsoft. Microsoft SEAL est écrit en C++ standard moderne et est facile à compiler et à exécuter dans de nombreux environnements différents. Microsoft SEAL est fourni au départ avec deux cryptosystèmes de chiffrement homomorphe BFV et CKKS et depuis sa version 4.1le crypto-système BGV a été ajouté.

La bibliothèque FHE Microsoft SEAL est multiplateforme, elle peut être utilisée sur:

Tabl 3.1 - Plateformes d'utilisation de SEAL

Système	Chaîne d'outils
Windows	Visual studio 2022 avec C++ et les outils CMake pour Windows
linux	Clang++ (>= 5.0) or GNU G++ (>= 6.0), CMake (>= 3.13)
macOS/iOS	Xcode chaîne d'outils(>= 9.3), CMake (>= 3.13)
Android	Android studio
FreeBSD	CMake (>= 3.13)

Il faut noter que Microsoft SEAL compilé avec Clang++ offre de bien meilleures performances d'exécution que celui compilé avec GNU G++.

Les dépendances facultatives de Microsoft SEAL sont les suivantes:

-- Intel HEXL

Intel HEXL(Homomorphic Encryption Acceleration Library)[13] est une bibliothèque fournissant des implémentations efficaces de primitives cryptographiques courantes dans le chiffrement homomorphe. L'accélération est particulièrement évidente sur les processeurs Intel dotés du jeu d'instructions Intel AVX512-IFMA52.

-- Microsoft GSL (Guidelines Support Library)

Microsoft GSL est une bibliothèque d'en-tête uniquement qui implémente un type de vue qui fournit un accès sécurisé (avec limites vérifiées) à la mémoire.

-- ZLIB et Zstandard

ZLIB et Zstandard sont des bibliothèques de compression largement utilisées. Microsoft SEAL peut utiliser ces bibliothèques pour compresser les données sérialisées. Zstandard est beaucoup plus rapide que ZLIB.

3.2.13 OpenFHE

OpenFHE [8] est une bibliothèque multiplateforme C++ disponible sous licence BSD 2 clauses qui inclut des implémentations efficaces de tous les cryptosystèmes FHE courants:

-- Cryptosystème de Brakerski/Fan-Vercauteren (BFV) pour l'arithmétique entière -- Schéma Brakerski-Gentry-Vaikuntanathan (BGV) pour l'arithmétique entière

3.2 Bibliothèques FHE 41

Mémoire de Master 2 Recherche 41 MOUYOUME DIEUDONNE(c) UYI

-- Cryptosystème Cheon-Kim-Kim-Song (CKKS) pour l'arithmétique des nombres réels (inclut

le bootstrap approximatif)

-- Cryptosystème Ducas-Micciancio (DM) et Chillotti-Gama-Georgieva-Izabachene (CGGI) pour

évaluer les circuits booléens et les fonctions arbitraires sur des espaces de texte en clair plus

grands à l'aide de tables de recherche

OpenFHE implémente des algorithmes efficaces de système de numérotation des résidus (RNS) pour

atteindre des performances élevées et Intel HEXL peut être utilisé pour accélérer évidemment les

calculs sur les processeurs Intel dotés du jeu d'instructions Intel AVX512-IFMA52.

La version actuelle (stable) est la v1.1.4 (publiée le 8 mars 2024).

OpenFHE est multiplateforme, elle peut être utilisée sur:

-- Linux

-- MacOS

-- Windows

3.2.14 PALISADE

PALISADE [21] est une bibliothèque multiplateforme C++ disponible sous licence BSD 2 clauses de cryptographie en treillis qui comprend actuellement des implémentations efficaces des capacités de cryptographie en treillis suivantes : BFV, BGV, CKSS, FHEW, et THFE.

La bibliothèque est basée sur une architecture modulaire avec les couches suivantes:

-- Couche d'opérations mathématiques prenant en charge l'arithmétique modulaire de bas niveau, les transformations théoriques des nombres et l'échantillonnage d'entiers. Cette couche est mise en oeuvre pour être portable sur plusieurs substrats de calcul matériels.

-- Couche d'opérations de treillis prenant en charge les opérations de treillis, l'algèbre en anneau et l'échantillonnage de trappes de treillis.

-- Couche crypto contenant des implémentations efficaces de schémas de cryptographie en treillis. Couche d'encodage prenant en charge plusieurs encodages de texte en clair pour les schémas cryptographiques.

Par défaut, la bibliothèque est construite sans dépendances externes, mais Intel HEXL peut être utilisé pour accélérer évidemment les calculs sur les processeurs Intel dotés du jeu d'instructions Intel AVX512-IFMA52. La version actuelle est la 1.11.9 (publiée le 2 décembre 2022).

PALISADE tourne sur les systèmes suivants:

-- FreeBSD

-- Ubuntu [16.04]

-- Arch Linux

-- Manjaro Linux

3.2 Bibliothèques FHE 42

TABLE 3.2 - Bibliothèques FHE

Bibliothèque FHE	Cryptosystèmes supportés	Langage de pro- grammation	Licence	Bootstrapping
SEAL	BGV,BFV,CKKS	C++/C sharp	MIT	NON
OpenFHE	BGV,BFV,CKKS, DM,CGGI	C++	BDS-2 clauses	OUI
PALISADE	BGV,BFV,CKKS, DM,CGGI	C++	BDS-2 clauses	OUI
HELib	BGV,CKKS	C++	Apache	OUI
HEAAN	CKKS	C++	Creativie Com- mons	OUI
Latigo	BGV,BFV,CKKS	Go	Apache 2.0	OUI
TenSEAL	BFV,CKKS	C++,Python		NON
PyFHE	BGV,BFV, CKKS	Python	OUI
TFHE	GSW	C,C++	Apache 2.0	OUI
FHEW	FHEW	C,C++	GNU	OUI

Mémoire de Master 2 Recherche 42 MOUYOUME DIEUDONNE(c) UYI

Mémoire de Master 2 Recherche 43 MOUYOUME DIEUDONNE(c) UYI

Chapitre IV

ETUDE DE L'EXISTANT

Dans ce chapitre, nous présentons les différents travaux existants sur la comparaison des bibliothèques FHE en se limitant surceux en rapport de notre étude.

1 L'étude de Safouane E. BENELKADI [11] fait une évaluation comparative des performances

de Microsoft SEAL et HELib dans le contexte de multiplication matricielle avec chiffrement

homomorphe, incluant une analyse d'algorithmes classiques et hybrides.

Contexte de l'étude

-- Évaluation des bibliothèques:

-- Microsoft SEAL (Simple Encrypted Arithmetic Library)

-- HELib (Homomorphic Encryption Library)

-- Algorithmes testés:

-- Approche classique « naïve »

-- Algorithme de Strassen optimisé

-- Algorithme hybride adaptatif

Méthodologie expérimentale

Configuration des tests

-- Matrices carrées A de dimension k = 2n

-- Opération : A X A avec implémentations:

-- Version non chiffrée

-- Versions chiffrées (SEAL/HELib)

Algorithme hybride

-- Logique adaptative seuillée :

Méthode =

????^?Strassen si k> kseuil ???? Naïve sinon

-- Optimisation de complexité : O(n³) ? O(n^2.81) Résultats comparatifs

Performances de SEAL contre HELib

-- Avantages SEAL:

-- Temps d'exécution réduit de 35-40% contre HELib -- Gestion optimisée du bruit cryptographique

CHAPITRE 4. ETUDE DE L'EXISTANT 44

Mémoire de Master 2 Recherche 44 MOUYOUME DIEUDONNE(c) UYI

-- Limitations SEAL:

-- Absence de système d'alerte pour le bruit résiduel

-- Nécessité de calibration manuelle

Analyse des limitations

Contraintes cryptographiques

-- Phénomène de « mort par bruit »

-- Facteurs d'atténuation:

-- Sélection de circuits de calcul courts

-- Bootstrapping cryptographique

Conclusion

Cette étude montre que dans le contexte des opérations matricielles, Microsoft SEAL démontre une supériorité temporelle par rapport à HELib, notamment pour la multiplication de matrices. Cette performance s'explique par une gestion optimisée du bruit cryptographique: SEAL permet des seuils de tolérance plus élevés avant que le bruit ne compromette les calculs. Cependant, cette bibliothèque présente une lacune opérationnelle majeure: elle n'alerte pas l'utilisateur lors d'échecs de déchiffrement causés par l'accumulation de bruit, imposant ainsi un contrôle manuel rigoureux des paramètres de sécurité.

2 Dans leur étude, Carlos Aguilar Melchor, Marc Olivier Kilijian, Cédric Lefebvre, and Thomas Ricosset [3] explorent l'utilisation de modules de texte clair (plaintext moduli) de grande taille avec trois bibliothèques FHE (SEAL, HElib-MP et FV-NFLlib) pour comparer leurs fonctionnalités et efficacité. Une adaptation spécifique a été nécessaire pour HElib, modifiée en HElib-MP afin de prendre en charge les modules multi-précision , tandis que les versions standard de SEAL (v2.3 pour des modules = 60 bits et v2.1 pour des modules supérieurs) et FV-NFLlib ont été utilisées sans modifications.

Bien qu'une approche basée sur le théorème des restes chinois permettrait des calculs multi-précision génériques, elle se révèle inadaptée aux cas nécessitant des modules spécifiques (ex. ECDSA/RSA), non factorisables de manière optimale.

Leur analyse compare les stratégies employées par ces bibliothèques pour gister le bruit cryptographique et les conversions de représentation, en mesurant leur impact sur les performances globales.

Paramètres expérimentaux:

Matériel : Un coeur d'un processeur Intel Xeon E5-2695 v3 (2,30 GHz). Sécurité : Configuration SHE garantissant= 128 bits via le script Albrecht-Player-Scott, aligné sur les standards de SEAL v2.3.

Extrapolation : Un doublement des exigences de sécurité n'augmenterait les coûts que linéairement, validant la généralisation de nos résultats à des niveaux de sécurité plus élevés. Cette méthodologie souligne les compromis entre flexibilité des modules, efficacité computa-

CHAPITRE 4. ETUDE DE L'EXISTANT 45

tionnelle et contraintes cryptographiques dans les implémentations FHE modernes. Principales conclusions de l'analyse de performance

1. Critères de sélection des bibliothèques

-- Pour logp = 1 :

-- SEAL v2.3 optimal jusqu'à une profondeur de calcul -12

-- Performance équivalente entre SEAL v2.3 et HElib (12-25)

-- Supériorité nette d'HElib au-delà de 25

-- Pour logp = 60 :

-- FV-NFLlib/SEAL v2.3 > HElib (jusqu'à -40)

-- Recommandation: SEAL v2.3 (développement actif + ergonomie)

-- Pour logp > 60 :

-- Cas 1 : Module factorisable (sous-modules 60 bits) - Approche CRT + SEAL v2.3

-- Cas 2 : Module premier/critptographique - FV-NFLlib (log q < 2000) ou HElib-MP

(log q > 2000)

2. Observations théoriques

-- Représentations non-CRT : Peu compétitives même avec Karatsuba

-- Comparaison BGV/FV :

-- Supériorité de BGV pour grands modules

-- Piste d'optimisation: Implémentation simplifiée basée sur NFLlib

-- Synergies technologiques:

-- Combinaison prometteuse : NFLlib + Approche FullRNS (Bajard et al.)

-- Potentiel d'amélioration -30% selon tests préliminaires

Recommandations stratégiques

-- Adapter l'architecture aux contraintes:

-- Profondeur < 25 : Privilégier HElib

-- Modules < 60 bits : SEAL v2.3

-- Modules critiques : Combinaison FV-NFLlib/HElib-MP

3 La recherche de Faneela 1 et al.[4] évalue les performances de deux bibliothèques de chiffrement entièrement homomorphe (FHE), SEAL (développée par Microsoft) et OpenFHE, en se focalisant sur les schémas BGV (optimisé pour les calculs exacts) et CKKS (spécialisé dans l'arithmétique approximative). L'objectif principal est de mesurer leurs surcoûts computation-nels, leur évolutivité et leur efficacité dans des environnements multi-plateformes (Windows et Linux). Les expériences, menées sur un ordinateur portable équipé d'un processeur Intel Core i7-8550U, de 16 Go de RAM et d'un SSD de 512 Go, ont comparé systématiquement le temps d'exécution et l'utilisation de la mémoire. Des paramètres cryptographiques clés - tels que le degré de polymodule, le module de coefficients et le facteur d'échelle - ont été ajustés dynamiquement pour refléter des scénarios opérationnels réalistes, notamment pour les multiplications homomorphes, dont la complexité nécessite des configurations adaptatives.

Résultats et observations

Mémoire de Master 2 Recherche 45 MOUYOUME DIEUDONNE(c) UYI

CHAPITRE 4. ETUDE DE L'EXISTANT 46

Mémoire de Master 2 Recherche 46 MOUYOUME DIEUDONNE(c) UYI

Les résultats démontrent une supériorité nette d'OpenFHE sur SEAL dans toutes les configurations testées. Par exemple, pour des multiplications à haute profondeur (degré de polymo-dule = 14), OpenFHE réduit le temps d'exécution de 20 à 35% grâce à une optimisation des opérations vectorielles et une gestion plus efficace du parallélisme. Par ailleurs, Linux s'est imposé comme la plateforme la plus performante, notamment pour la gestion de la mémoire cache et l'exploitation des coeurs CPU, surpassant Windows dans tous les cas de figure. Concernant les schémas, BGV a montré une stabilité remarquable pour les calculs exacts à grande échelle, tandis que CKKS, bien que flexible, exige des ajustements fréquents du facteur d'échelle pour maintenir la précision des résultats, ce qui complexifie son déploiement dans des applications temps réel.

Implications et perspectives

Ces conclusions soulignent l'importance critique du choix combiné de la bibliothèque, du schéma FHE et du système d'exploitation pour les applications sensibles à la latence. Les performances d'OpenFHE suggèrent son adoption privilégiée dans les architectures modernes, notamment pour les systèmes cloud ou les calculs distribués. Toutefois, des défis persistent, comme l'optimisation des paramètres cryptographiques pour CKKS ou l'intégration de bootstrapping (rechargement des chiffrés) dans des workflows complexes.

Conclusion

En conclusion, cette étude non seulement valide OpenFHE comme référence actuelle en FHE, mais aussi met en lumière les interactions subtiles entre paramètres cryptographiques, matériels et logiciels. Les pistes proposées, combinées à l'évolution rapide des architectures matérielles, pourraient accélérer l'adoption du chiffrement homomorphe dans des secteurs où la confidentialité est non négociable, comme la santé ou la finance décentralisée.

4 L'étude de Thi Van Thao DOAN et al.[24] vise à présenter aux lecteurs les principes fondamentaux des schémas de chiffrement homomorphe (HE) sans entrer dans des détails mathématiques complexes.

Analyse comparative

Cet article propose une comparaison théorique et pratique exhaustive des principaux schémas

HE, couvrant les trois catégories existantes:

-- FHE (chiffrement entièrement homomorphe)

-- SWHE (chiffrement partiellement homomorphe à capacités limitées)

-- PHE (chiffrement partiellement homomorphe)

Méthodologie d'analyse

Pour chaque famille de schémas, nous analysons:

-- Les paramètres d'entrée et leurs contraintes opérationnelles

-- Les compromis sécurité/performance via une méthodologie comparative

Bénéfices pratiques

Cette approche permet aux praticiens non experts de :

CHAPITRE 4. ETUDE DE L'EXISTANT 47

-- Distinguer les propriétés des bibliothèques existantes

-- Faciliter leur intégration dans des projets HE personnalisés Étude expérimentale

Composant Détails

Bibliothèques testées SEAL , PALISADE , HELib, HEAAN

Implémentations personnelles Paillier, ElGamal, RSA (pour les schémas PHE non disponibles dans les bibliothèques open-source)

Méthodologie Mesures de performance par cas d'usage avec interprétation

des résultats

Analyse de sécurité

Une évaluation rigoureuse couvre:

-- Résistance aux attaques IND-CPA et IND-CCA

-- Vulnérabilités face à la factorisation entière sur:

-- Ordinateurs classiques

-- Ordinateurs quantiques

Conclusion

Cette étude fournit ainsi un cadre opérationnel pour le choix éclairé de schémas HE selon les

contraintes applicatives.

5 L'étude Shereen Mohamed Fawaz, Nahla Belal, Adel ElRefaey, Mohamed Waleed Fakhr [29] évalue les performances des schémas BFV (exact) et CKKS (approximatif) via la bibliothèque Microsoft SEAL, en se concentrant sur trois opérations arithmétiques homomorphes : addition, multiplication et mise au carré de vecteurs. L'étude intègre une analyse temporelle détaillée et une gestion critique du bruit cryptographique.

Méthodologie expérimentale

Les expériences sont réalisées avec des vecteurs de taille 2ⁿ et des paramètres de chiffrement adaptés à chaque schéma:

-- BFV : Paramètres incluant le degré du polynôme modulus (2ⁿ ), le modulus du texte chiffré et le modulus du texte en clair.

-- CKKS : Paramètres similaires mais sans modulus du texte en clair, utilisant une technique d'encodage différente.

Résultats clés

Comparaison des temps d'exécution:

-- Multiplication BFV : Nécessite 5 étapes (encodage, chiffrement, multiplication, déchiffrement, décodage). Le temps total augmente avec la taille des vecteurs, les étapes les plus coûteuses étant le chiffrement (4720us pour 4096 éléments) et la multiplication.

-- Addition BFV : Moins coûteuse que la multiplication (62us contre 4720us pour 4096 éléments).

-- CKKS : L'encodage et le chiffrement dominent le temps d'exécution, avec des performances variables selon la taille des vecteurs.

Mémoire de Master 2 Recherche 47 MOUYOUME DIEUDONNE(c) UYI

CHAPITRE 4. ETUDE DE L'EXISTANT 48

Impact du bruit et relinéarisation :

La multiplication séquentielle réduit progressivement le budget de bruit. Le BFV permet 3 multiplications séquentielles pour 4096 éléments grâce à la relinéarisation, une technique réduisant la taille des textes chiffrés (au prix d'un coût computationnel élevé). Le CKKS ne permet que 2 multiplications pour la même taille. Pour les grandes tailles de vecteurs (8192, 16384), le CKKS devient moins performant que le BFV en termes de multiplications séquentielles.

Performances comparées BFV et CKKS :

-- Addition : BFV surpasse CKKS pour toutes les tailles.

-- Mise au carré : BFV est plus rapide pour 4096 et 8192 éléments, mais CKKS légèrement meilleur pour 16384.

-- Multiplication : BFV reste plus efficace globalement.

Cette étude souligne l'arbitrage entre précision (BFV) et flexibilité (CKKS), tout en mettant en avant l'impact critique de l'optimisation des paramètres et de la gestion proactive du bruit. Les résultats orientent le choix de schéma selon les cas d'usage, avec des pistes prometteuses pour l'intégration du FHE dans l'infrastructure de calcul sécurisé.

6 L'étude de Kim et al. [36], publiée en 2021 propose une analyse comparative des schémas de chiffrement homomorphe BGV et BFV, avec des variantes améliorées implémentées dans la bibliothèque PALISADE. Nous démontrons un contrôle optimal du bruit cryptographique selon les paramètres opérationnels, combinant évaluation théorique et benchmarks expérimentaux. Les résultats révèlent des compromis performance/précision dépendant du module de texte en clair t, avec des gains allant jusqu'à 4× en multiplication homomorphe.

Contexte et Objectifs

Leurs travail s'inscrit dans l'optimisation des schémas HE de seconde génération. Les

objectifs clés incluent:

-- Implémentation unifiée des variantes BGV/BFV dans PALISADE

-- Analyse comparative de la complexité computationnelle

-- Évaluation empirique via des benchmarks reproductibles

Méthodologie

Implémentation PALISADE

Ils ont développé des modules spécifiques intégrant:

BFV optimisé: E(m) = (c0,c1) ? ZQ[X]/(Xⁿ + 1)² (4.1)

avec gestion adaptative du modulus Q selon le profil de bruit.

Comparaison théorique

Pour les opérations primaires , ils analysent: -- Coût en multiplications modulaires

Mémoire de Master 2 Recherche 48 MOUYOUME DIEUDONNE(c) UYI

CHAPITRE 4. ETUDE DE L'EXISTANT 49

Mémoire de Master 2 Recherche 49 MOUYOUME DIEUDONNE(c) UYI

-- Profondeur de réduction de bruit

-- La taille des clés dérivées

Résultats

Contrôle du bruit

Leur variante BFV réduit l'expansion de bruit de 15% vs. BGV pour t > 2²⁰, inversant les

tendances antérieures.

Performances opérationnelles

-- BFV : 2.1× plus rapide pour t = 2 (OPérations/s)

-- BGV : Supériorité à partir de t = 210

-- Multiplication homomorphe : 4× accélération sur 10 niveaux

Conclusion

Leurs implémentation unifiée démontre la complémentarité des schémas selon les cas d'usage. La version modifiée du schéma BFV surpasse BGV en termes de gestion du bruit cryptographique, quel que soit le module de texte en clair (t), contrairement aux conclusions antérieures [14,15] qui favorisaient BGV pour les grands modules. Cette amélioration découle essentiellement des ajustements apportés au processus de chiffrement BFV. Par ailleurs, BFV démontre une nette supériorité en vitesse pour les petits modules (ex. t=2), alors que BGV devient compétitif avec l'augmentation de t, à condition que ses modules CRT ne soient pas agrégés.

La variante BGV proposée ici vise spécifiquement à simplifier son utilisation, historiquement plus complexe que BFV. Son ergonomie atteint désormais le niveau de l'implémentation BFV dans PALISADE, bien que cette accessibilité accrue impose des compromis techniques (ex. sélection plus restrictive des tailles de modules CRT). Pour une évaluation équitable des performances, une implémentation unifiée dans PALISADE du modèle BGV à estimation dynamique de bruit (tel qu'implémenté dans HElib) s'avérerait nécessaire, évitant ainsi les biais liés aux différences d'optimisation des opérations primitives (comme les NTT).

7 Sidorov et al. [48] dans leur étude compare les performances opérationnelles de cinq cryp-tosystèmes homomorphes (HElib, SEAL, PyAono, Paillier et ElGamal) sur des opérations élémentaires. Les résultats révèlent des écarts significatifs de performance entre les schémas partiellement et totalement homomorphes, avec des implications pratiques pour leur adoption industrielle.

Méthodologie expérimentale

-- Opérations testées : Addition, soustraction, multiplication

-- Exclusion de la division:

-- Non supportée par SEAL, PyAono et Paillier

-- Équivalence fonctionnelle dans ElGamal (a b = a X b^-1)

CHAPITRE 4. ETUDE DE L'EXISTANT 50

Mémoire de Master 2 Recherche 50 MOUYOUME DIEUDONNE(c) UYI

-- Paramètres:

? ? ?_????Nombres testés: 1000 paires de nombres à 2 chiffres

?

?_???Répétitions : 5 itérations par test ????? Bootstrapping : Désactivé

Analyse comparative

Tabl 4.1 - Performances relatives par cryptosystème

Système	Avantages	Limites
Paillier	-- Addition/soustraction: 1.2e - 5s -- Génération de clé : 0.4s	Multiplication lente (2.1e - 3s)
ElGamal	Multiplication optimale (1.8e - 7s)	Chiffrement :(5.2e - 4s)
HElib	Chiffrement efficace (7.8e - 4s)	Déchiffrement: (1.3s)

Conclusion

L'analyse des résultats agrégés révèle une conclusion claire : les cryptosystèmes partiellement homomorphes présentent dès aujourd'hui un potentiel d'application pratique dans des cas d'usage spécifiques. À l'inverse, les schémas totalement homomorphes - bien que théoriquement révolutionnaires - ne répondent pas encore aux exigences opérationnelles en termes de performance et de maturité technologique.

Cette dichotomie souligne un paradoxe contemporain: les solutions cryptographiques les plus polyvalentes (FHE) restent prisonnières de leurs limitations computationnelles, tandis que des approches moins ambitieuses sur le plan théorique (PHE) s'avèrent paradoxalement plus adaptées aux implémentations réelles.

CHAPITRE 4. ETUDE DE L'EXISTANT 51

Mémoire de Master 2 Recherche 51 MOUYOUME DIEUDONNE(c) UYI

TABLE 4.2 - Syntèse sur l'étude de l'existant des bibliothèques FHE

Auteurs	Description	Schémas	Bibliothèques
Carlos Aguilar et al.,2019	Comparison des biblio- thèques homomorphes	BGV, BFV	SEAL,HELlib-MP,FV-NFLlib
Safouane ,2020	Comparaison des bi- bliothèques	-	SEAL,HELlib
A. Kim et al., 2021	Amélioration du schéma BFV et analyse BGV	BGV, BFV	PALISADE
Shereen Moha- med Fawaz et al.,2001	Evaluation des perfor- mances	BFV,CKKS	SEAL
V. Sidorov et al., 2022	Évaluation des perfor- mances pour applica- tions réelles	Paillier, El-Gamal, SEAL, PyAono, HElib	-
Thi Van Thao DOAN et al., 2023	Revue des implémen- tations de schémas de chiffrement homo-morphe	BGV, BFV,CKKS	SEAL, PALI- SADE,HELlib,HEAAN

Au regard de ce qui précède, nous proposons une comparaison de performance des bibliothèques homomorphes Microsoft SEAL, OpenFHE et PALISADE en utilisant les cryptosystème BGV et BFV en se focalisant sur la multiplication de deux matrices carrées et en mesurant à chaque fois les temps de calcul du chiffrement, de la multiplication sur homomorphes et du déchiffrement.

Mémoire de Master 2 Recherche 52 MOUYOUME DIEUDONNE(c) UYI

Chapitre V

IMPLEMENTATION ET RÉSULTATS

Dans ce chapitre, nous justifions le choix des bibliothèques FHE et des crytptosystèmes qu'elles implémentent ensuite nous donnons les différentes procédures d'installation de ces bibliothèques FHE et en fin nous faisons des tests et discutons des résultats obtenus.

5.1 Choix des cryptosystèmes FHE

5.1.1 Classes de calculs HFE

Il est important de choisir la bonne approche pour un calcul FHE. On distingue trois classes [9] de calculs FHE :

1 Circuits booléens

Les données en texte brut sont représentées sous forme de bits et les calculs sont exprimés

sous forme de circuits booléens.

Ces caractéristiques sont:

-- La comparaison rapide des nombres

-- La prise en charge les circuits booléens arbitraires

-- L'amorçage rapide (procédure de rafraîchissement du bruit)

Les cryptosystèmes concernés sont : GSW, FHEW et TFHE.

2 Arithmétique modulaire (exacte)

Les données sont en texte brut sont représentées sous forme d'entiers modulo un module de

texte en clair p (ou leurs vecteurs) et les calculs exprimés en entier arithmétique modulo p

Ces caractéristiques sont:

-- Les calculs SIMD efficaces sur des vecteurs d'entiers (en utilisant le batching)

-- L'arithmétique entière rapide et de haute précision

-- La récupération rapide d'informations privées/intersection d'ensembles privés

-- Conception nivelée (souvent utilisée sans bootstrapping)

Les cryptosystèmes concernés sont : BGV et BFV.

3 Arithmétique des nombres approximatifs

Les données en texte brut sont représentées sous forme de nombres réels (ou de nombres complexes) et le modèle de calcul similaire à l'arithmétique à virgule flottante, mais traitant

5.1 Choix des cryptosystèmes FHE 53

Mémoire de Master 2 Recherche 53 MOUYOUME DIEUDONNE(c) UYI

de nombres à virgule fixe.

Ces caractéristiques sont:

-- Les calculs SIMD efficaces sur des vecteurs de nombres réels (en utilisant le batching)

-- L'approximation polynomiale rapide

-- L'inverse multiplicatif et transformée de Fourier discrète relativement rapides

-- Les calculs approximatifs approfondis, tels que l'apprentissage par régression logistique

-- La conception nivelée (souvent utilisée sans bootstrapping)

Le cryptosystème concerné est: CKKS

Ce qui précède nous amène à choisir les cryptosystèmes BFV [35] et BGV [7] implémentés dans les bibliothèques homomorphiques Micorsoft SEAL, OpenFHE et PALISADE parce que c'est une classe de FHE qui prend en charge l'arithmétique modulaire sur des champs finis, qui correspondent généralement à des vecteurs d'entiers mod p, où p est un nombre premier ou une puissance première, communément appelé le module du texte en clair. Cette classe est également parfois utilisée pour l'arithmétique des petits nombres entiers. De nos jours, les schémas homomorphes BFV et BGV semblent susciter plus d'attention [30].

En outre, de manière spécifique sur le calcul matriciel, ces deux cryptosystèmes ont les caractéristiques respectives:

BFV (Brakerski-Fan-Vercauteren)

-- Efficacité pour les opérations arithmétiques

Le cryptosystème BFV est particulièrement adapté aux opérations arithmétiques homomorphes, telles que l'addition et la multiplication, qui sont essentielles dans les calculs matriciels. Il permet de réaliser ces opérations de manière efficace, ce qui est crucial pour les performances du calcul matriciel.

-- Support de la multiplication homomorphe

Le cryptosystème BFV offre un support natif pour la multiplication homomorphe, ce qui facilite la réalisation de la multiplication matricielle. Cela permet d'effectuer des calculs matriciels complexes sans avoir à décomposer la multiplication en opérations plus simples, ce qui simplifie le processus de programmation.

-- Contrôle sur la profondeur du circuit

Le cryptosystème BFV permet de contrôler la profondeur du circuit homomorphe, ce qui est important pour les calculs matriciels de grande taille. En réduisant la profondeur du circuit, on peut réduire la complexité et le temps d'exécution des opérations matricielles.

BGV (Brakerski-Gentry-Vaikuntanathan)

-- Support de la multiplication homomorphe Le cryptosystème BGV permet également la multiplication homomorphe, ce qui en fait un choix approprié pour les calculs de multiplication matricielle. Il permet de manipuler les matrices chiffrées et d'effectuer des opérations matricielles complexes tout en préservant la confidentialité des données.

-- Support de la multiplication par constante

Le cryptosystème BGGV offre une fonctionnalité supplémentaire importante pour les calculs

5.1 Choix des cryptosystèmes FHE 54

Mémoire de Master 2 Recherche 54 MOUYOUME DIEUDONNE(c) UYI

matriciels, à savoir la multiplication par constante homomorphe. Cela permet de multiplier une matrice chiffrée par une constante sans avoir à chiffrer la constante elle-même, ce qui simplifie les calculs matriciels.

-- Capacité à gérer des schémas plus généraux

Le cryptosystème BGV est un schéma plus général qui permet de prendre en charge un large éventail de calculs homomorphes, y compris les calculs matriciels. Il offre une plus grande flexibilité et peut être adapté à des applications plus complexes nécessitant des opérations non arithmétiques.

5.1.2 Choix des paramètres de chiffrement

L'instanciation de tout cryptosystème de chiffrement homomorphe ou non nécessite de définir certains paramètres, par exemple pour déterminer la taille de la clé ou le niveau de sécurité. Dans le cadre du chiffrement homomorphique, les paramètres influencent non seulement la sécurité, mais également le type de texte en clair et les calculs pouvant être effectués.

Paramètres principaux

-- Module du texte en clair p

Il détermine la taille maximale des valeurs pouvant être chiffrées. Il doit être suffisamment grand pour contenir les résultats des opérations intermédiaires sans overflow.

-- Module du texte chiffré q

C'est le paramètre fonctionnel qui détermine le nombre de calculs autorisés (la quantité de bruit pouvant être tolérée). Il est souvent défini implicitement en utilisant la valeur de profondeur multiplicative spécifiée par l'utilisateur

-- Dimension du texte chiffré n

C'est la valeur minimale qui est calculée en fonction du niveau de sécurité souhaité et du module de texte chiffré q. C'est aussi la taille du vecteur d'entiers chiffrés lorsqu'un emballage standard ou à coefficients est utilisé.

Paramètres de sécutité

En général, le niveau de sécurité ë augmente à mesure que n augmente et diminue à mesure que q augmente [17]. D'un autre côté, plus q est grand, plus les calculs complexes peuvent être effectués sur les textes chiffrés du schéma de chiffrement : les textes chiffrés de ces schémas de chiffrement contiennent une composante de bruit (qui est importante pour la sécurité), et ce bruit augmente à chaque opération. Le résultat chiffré ne peut être déchiffré que si le bruit est inférieur à q, donc l'utilisation de valeurs de q plus grandes implique que nous pouvons effectuer plus d'opérations.

La dimension du texte chiffré (degré de polynôme) doit être choisie en fonction de la table de sécurité publiées sur HomomorphicEncryption.org [6].

Les paramètres retenus pour notre étude sont consignés dans le tableau 5.1

5.2 Choix des bibliothèques FHE 55

Mémoire de Master 2 Recherche 55 MOUYOUME DIEUDONNE(c) UYI

FIGURE 5.1 - Sélection des paramètres

Paramètres	SEAL	OpenFHE	PALISADE
n	8192	8192	8192
p	65537	65537	65537
logq	218	240	180
l		1,2,3	1,2,3
A	128 bits	128 bits	128 bits

TABLE 5.1 - Paramètres de chiffrement

5.2 Choix des bibliothèques FHE

Le choix d'une bibliothèque FHE obéit à certains critères parmi lesquels les plus importants sont:

1 La disponibilité des informations

La manière dont une bibliothèque FHE présente les informations est très importante. Trop d'informations laisse l'utilisateur submergé et il finit par sauter du texte important, mais présenter trop peu d'informations laisse l'utilisateur confus et incapable d'utiliser correctement la bibliothèque.

2 La taille de la communauté

Une communauté plus grande signifierait plus d'innovation de la part des utilisateurs, de plus grande communauté d'utilisateurs de bibliothèque FHE signifierait qu'il y aurait plus de personnes qui pourraient aider un utilisateur tiers avec les bugs obtenus et clarifier ses malentendus. Par exemple, il existe un portage d'OpenFHE vers WebAssembly, créé par certains membres de la communauté. De telles contributions sont moins susceptibles de se produire s'il n'existe pas une communauté importante autour de la bibliothèque de chiffrement homo-morphe.

3 L'engagement communautaire

5.3 Installation des bibliotèques FHE 56

Mémoire de Master 2 Recherche 56 MOUYOUME DIEUDONNE(c) UYI

Les bibliothèques FHE peuvent progressivement se déprécier ou devenir obsolètes. Il est compréhensible que cela se produise : héberger un projet open source réussi est difficile et prend du temps. Cependant un utilisateur doit être sûr la bibliothèque FHE sera toujours disponible dans quelques mois ou années et soit à mise à jour.

4 L'open source

Ce critère est considéré comme non négociable que la bibliothèque du chiffrement homo-morphe soit open source. Car une bibliothèque de chiffrement homomorphe qui n'utilise pas de code open source n'est pas intéressée à aider la communauté. Plus d'attention sur le code se traduirait par un code plus sûr, car vous êtes plus susceptible de détecter ces erreurs.

5 La conformité aux normes

Une bibliothèque doit être conforme aux normes. Étant donné que les cryptographes s'in-quiètent des pires scénarios, il n'est pas surprenant qu'il soit essentiel d'établir des normes de sécurité. Après tout, si les algorithmes de cryptographie ne sont pas sécurisés, alors les programmes construis à partir de ces bibliothèques ne le sont pas, or la sécurité est essentielle en cryptographie. Il existe toute une organisation nommée Homomorphic Encryption Standardization [6] qui établit des descriptions de cryptosystèmes, des descriptions détaillées de leurs propriétés de sécurité et leurs paramètres sécurisés.

De ce qui précède, nous avons choisi d'utiliser dans notre travail les bibliothèques FHE open-source Microsoft SEAL [47] version 4.1.1, OpenFHE [8]version 1.1.1 (publiée le 23 août 2023) et PALISADE [21]version 1.11.9

5.2.1 Environnement

Les bibliothèques FHE : Microsoft SEAL, OpenFHE et PALISADE étant toutes multiplateformes, nous avons opté d'utiliser l'environnement Ubuntu 20.04 LTS avec 4 × 216.8 MHz CPU qui est plus accessible pour exécuter nos programmes et de faire nos différents tests, de plus il permet facilement d'installer les paquets des prérequis dont les bibliothèques ont besoin en tapant les commandes des prérequis dont les bibliothèques ont besoin.

5.2.2 Langage de programmation et éditeurs utilisés

Les bibliothèques FHE : Microsoft SEAL, OpenFHE et PALISADE étant écrites en un langage commun qui est le C++, nous avons naturellement utilisé ce même langage pour écrire nos programmes afin de faciliter leurs interactions. Quant aux éditeurs de texte, nous avons utilisé Vim et Notepad++ pour l'écriture de nos programmes.

5.3 Installation des bibliotèques FHE

Les bibliothèques FHE : Microsoft SEAL, OpenFHE et PALISADE étant toutes open-source, il faut au préalable télécharger en ligne les différents dépôts Github [47] et suivre les étapes d'installa-

5.3 Installation des bibliotèques FHE 57

tion.

5.3.1 Installation de SEAL Version 4.1.1

· Pré-requis

Clang++ (>= 5.0) ou GNU G++ (>= 6.0), CMake (>= 3.13) Pour installer CMaKE

sudo apt -get install cmake

· Installation de git

Pour installer git pour le clonage

-- sudo apt -get update && sudo apt -get -y install git

-- sudo apt -get update && sudo apt -get build install-essential

· Etapes d'installation de SEAL

1 Pour cloner le dépôt de SEAL dans Github git clone https :// github.com/microsoft/SEAL.git

2 Pour spécifier le compilateur C++ de SEAL

cd SEAL cmake DCMAKE_CXX_COMPILER=/usr/bin/C++ -S . -B build

3 Pour installer SEAL dans un dossier local ex : SEAL

cmake -S . -B build -DCMAKE_INSTALL_PREFIX=/SEAL .. sudo cmake - -install build

5.3.2 Installation de OpenFHE

· Pré-requis

Clang++ (>= 5.0) ou GNU G++ (>= 6.0), CMake (>= 3.13) Pour installer CMake

sudo apt -get install cmake

· Installation de git

Pour installer git pour le clonage

-- sudo apt -get update && sudo apt -get -y install git

-- sudo apt -get update && sudo apt -get build install-essential

· Étapes d'installation de OpenFHE

1 Pour cloner le dépôt de OpenFHE[8] dans Github

git clone https :https :// github.com/openfheorg/openfhe-development.git

Mémoire de Master 2 Recherche 57 MOUYOUME DIEUDONNE(c) UYI

5.4 Multiplication Matricielle 58

Mémoire de Master 2 Recherche 58 MOUYOUME DIEUDONNE(c) UYI

2 Créer un répertoire dans lequel les binaires seront construits. Le choix typique est un sous-

dossier "build". Dans ce cas, les commandes sont:

-- mkdir build

-- cd build

-- cmake .

-- make

Pour choisir un emplacement d'installation en exécutant cmake -DCMAKE_INSTALL_PREFIX=/your/path

5.3.3 Installation de PALISADE

· Installer les prérequis

Pour g++

-- sudo apt-get install build-essential

-- sudo apt-get install cmake

-- sudo apt-get install autoconf

· Étapes d'installation de PALISADE

1 Pour cloner le dépôt

git clone https :// gitlab.com/palisade/palisade-release.git

2 Pour créer un répertoire où les binaires seront construit

Le choix typique est un sous-dossier "build".

Dans ce cas, les commandes sont:

-- mkdir build

-- cd build

-- cmake ..

3 Pour construire PALISADE make

4 Pour installer PALISADE dans un répertoire système make install

5.4 Multiplication Matricielle

5.4.1 Algorithme de multiplication matricielle na·ive

Soient deux matrices carrées A E ^nxn et B E ^nxn, le produit matriciel C = A x B s'obtient par:

cij = _Xn aik x bk _j pour 1 ~ i ~ n, 1 ~ j ~ n k=1

5.4 Multiplication Matricielle 59

Mémoire de Master 2 Recherche 59 MOUYOUME DIEUDONNE(c) UYI

Algorithm 3 Multiplication matricielle naïve

Fonction ProduitMatriciel(A, B) Entrée: A ? R^n×n, B ? Rn×n

Sortie : C ? R^n×n tel que C = A × B début

C ? 0n×n pour i ? 1 to m faire pour j ? 1 to n faire

pour k ? 1 to n faire

C[i, j] ? C[i, j] + A[i, k] × B[k, j]

Retourner C

La complexité temporelle est en O(n³).

5.4.2 Algorithme de multiplication homomorphe matricielle

Algorithm 4 Algorithme de multiplication matricielle homomorphe

Entrée: M1, M2 ? Z^n×n, A (paramètre de sécurité)

Sortie : M3 = M1 × M2

Fonction MultFHE(A)

début

Génération des clés

(pk, sk) ? KeyGen(A)

Phase de chiffrement

pour i ? [1, n] faire

pour j ? [1,n] faire

Qmⁱ₁^j Enc(pk, M1[i, j]) Qmⁱ₂^j Enc(pk, M2[i, j])

Calcul homomorphe

pour i ? [1, n] faire

pour j ? [1,n] faire

Jci jK ?1101] pour k ? [1, n] faire

Jci jK ?FHE-Add(QcijK, FHE-Mult(Qm^ik₁]], Qm^k₂^jK))

Phase de déchiffrement pour i ? [1, n] faire

pour j ? [1,n] faire

M3[i, j] ? Dec(sk, QcijK)

retourner M3

La complexité temporelle de cet algorithme est en O(n³).

5.5 Tests 60

Mémoire de Master 2 Recherche 60 MOUYOUME DIEUDONNE(c) UYI

5.5 Tests

Pour les tests, nous avons créé dans chaque dossier contenant le script .cpp un CMakeList.txt. La compilation et l'exécution de chaque projet se font en suivant les étapes suivantes:

5.5.1 Le cas de SEAL

Il suffit de suivre les étapes suivantes:

1 cd SEAL

2 cd nom du dossier du projet

3 sudo cmake -S . B build

4 sudo cmake build build

5 sudo cmake install build

6 ./nom de l'exécutable

5.5.2 Le cas de OpenFHE

Il suffit de suivre les étapes suivantes:

1 cd Openfhe-development

2 cd nom du dossier du projet

3 mkdir build

4 cd build

5 sudo cmake ..

6 sudo make

7 ./nom de l'exécutable

5.5.3 Le cas de PALISADE

Il suffit de suivre les étapes suivantes:

1 cd palisade

2 cd nom du dossier du projet

3 mkdir build

4 cd build

5 sudo cmake ..

6 sudo make

7 ./nom de l'exécutable

5.6 Exécution des programmes 61

Mémoire de Master 2 Recherche 61 MOUYOUME DIEUDONNE(c) UYI

5.6 Exécution des programmes

Dans cette section, nous montrons comment les différents programmes sont exécutés au cas par cas.

5.6.1 Cas de SEAL

Pour le cas de SEAL avec les cryptosystèmes BGV et BFV, les figures 5.2 et 5.3 ci-dessous montrent les étapes à suivre pour exécuter les différents programmes.

FIGURE 5.2 - Exécution du programme avec BGV FIGURE 5.3 - Exécution du programme avec BFV

5.6.2 Cas de OpenFHE

Pour le cas de OPENFHE avec les cryptosystèmes BGV et BFV les figures 5.4 et 5.5 ci-dessous montrent les étapes à suivre pour exécuter les différents programmes.

FIGURE 5.4 - Exécution du programme avec BGV FIGURE 5.5 - Exécution du programme avec BFV

5.7 Résultats obtenus et discussions 62

Mémoire de Master 2 Recherche 62 MOUYOUME DIEUDONNE(c) UYI

5.6.3 Cas de PALISADE

Pour le cas de PALISADE avec les cryptosystèmes BGV et BFV les figures 5.6 et 5.7 ci-dessous montrent les étapes à suivre pour exécuter les différents programmes.

Figure 5.6 - Exécution du programme avec BGV Figure 5.7 - Exécution du programme avec BFV

5.7 Résultats obtenus et discussions

Les différents tests ont été réalisés sur des matrices carrées de dimensions 2 X 2, 4 X 4, 6 X 6, 8 X 8 et 10 X 10 avec les coefficients choisis de manière aléatoire dans l'intervalle [0, 100]. Pour chaque dimension de la matrice, on a obtenu les moyennes de temps de chiffrement ,les moyennes de temps de la multiplication matricielle des deux matrices chiffrées et les moyennes des temps du déchiffrement des deux matrices après multiplication des deux matrices chiffrées après 100 itérations en utilisant les cryptosystèmes BFV et BGV suivants les paramètres de la table 5.1 en utilisant les bibliothèques FHE Microsoft SEAL version 4.1.1, OpenFHE version 1.0.4 et PALISADE version 1.11.9.

Ces tests nous ont permis d'avoir les différentes courbes ci-dessous qui représentent sur l'axe de abscisse les dimension des matrices et sur l'axe des ordonnées les moyennes des temps du chiffrement, de la multiplication, du déchiffrement et de la somme des moyennes de temps du chiffrement, de la multiplication et du déchiffrement.

5.7 Résultats obtenus et discussions 63

5.7.1 Utilisation du cryptosystème BFV

5.7.1.1 Temps du chiffrement, de la multiplication et du déchiffrement

Mémoire de Master 2 Recherche 63 MOUYOUME DIEUDONNE(c) UYI

Figure 5.8 - Temps du chiffrement Figure 5.9 - Temps de la multiplication

Figure 5.10 - Temps du déchiffrement	Figure 5.11 - Temps du chiffrement+ déchiffre-ment+multiplication

D'après la figure 5.2, il ressort que la moyenne des temps du chiffrement des deux matrices sur l'ensemble des différentes dimensions 4 X 4, 6 X 6, 8 X 8 et 10 X 10 des matrices est plus élevée dans OpenFHE que dans Mircosoft SEAL et dans PALISADE qui ont pratiquement une même évolution de temps sur l'ensemble des différentes dimensions des matrices.

D'après la figure 5.9, nous notons que la moyenne des temps des multiplications homomorphiques des deux matrices dans les différentes dimensions 4 X 4, 6 X 6, 8 X 8 et 10 X 10 des matrices dans Microsoft SEAL est plus élevée que dans PALISADE et dans OpenFHE.

D'après la figure 5.4, la moyenne des temps du déchiffrement des deux matrices chiffrées après leurs multiplications sur l'ensemble des différentes dimensions 4 X 4, 6 X 6, 8 X 8 et 10 X 10 des matrices est plus très élevée dans Microsoft SEAL que dans OpenFHE et dans PALISADE dont elle est presque la même.

5.7 Résultats obtenus et discussions 64

Mémoire de Master 2 Recherche 64 MOUYOUME DIEUDONNE(c) UYI

En conclusion, la figure 5.11, il ressort que la somme des moyennes des temps pour le chiffrement des deux matrices, la multiplication des deux matrices chiffrées et du déchiffrement sur les différentes dimensions 4 x 4, 6 x 6, 8 x 8 et 10 x 10 des matrices est plus élevée dans Microsoft SEAL que dans PALISADE et dans OpenFHE.

5.7.2 Utilisation du cryptosystème BGV

5.7.2.1 Temps du chiffrement, de la multiplication et du déchiffrement

FIGURE 5.12 - Temps du chiffrement FIGURE 5.13 - Temps de la multiplication

FIGURE 5.14 - Temps du déchiffrement	FIGURE 5.15 - Temps du chiffrement+ déchiffre-ment+multiplication

D'après la figure 5.12, il ressort que la moyenne des temps du chiffrement des deux matrices sur l'ensemble des différentes dimensions 4 x 4, 6 x 6, 8 x 8 et 10 x 10 des matrices est plus élevée dans OpenFHE que dans PALISADE et dans Mircosoft SEAL. L'écart est de plus en plus grand au fur et à mesure que les dimensions des matrices augmentent.

D'après la figure 5.13, il ressort que la moyenne des temps des multiplications homomorphiques des deux matrices dans les différentes dimensions 4 x 4, 6 x 6, 8 x 8 et 10 x 10 des matrices dans

5.7 Résultats obtenus et discussions 65

Mémoire de Master 2 Recherche 65 MOUYOUME DIEUDONNE(c) UYI

OpenFHE est plus élevée que dans PALISADE et dans Microsoft SEAL. Mais avec le temps de microsoft SEAL qui est presque linéaire et avec un écart qui se crée aussi considérablement avec les autres bibliothèques FHE.

D'après la figure 5.14, la moyenne des temps du déchiffrement des deux matrices chiffrées après leurs multiplications sur l'ensemble des différentes dimensions 4 x 4, 6 x 6, 8 x 8 et 10 x 10 des matrices est plus très élevée dans OpenFHE que dans PALISADE et dans Microsoft SEAL. L'écart est de plus en plus grand au fur et à mesure que les dimensions des matrices augmentent.

En conclusion, la figure 5.15, il ressort que la somme des moyennes des temps pour le chiffrement des deux matrices, la multiplication des deux matrices chiffrées et du déchiffrement sur les différentes dimensions 4x4, 6x6, 8x8 et 10x10 des matrices est plus élevé dans OpenFHE que dans PALISADE et dans Microsoft SEAL. L'écart est de plus en plus grand au fur et à mesure que les dimensions des matrices augmentent.

De manière générale, le cryptoystème Brakerski/Fan-Vercauteren (BFV) :

-- Le message est codé dans les bits de poids fort.

-- Le module du texte chiffré est constant alors que le bruit augmente à chaque opération. -- Possède une opération de multiplication homomorphique coûteuse

Contrairement au cryptosystème de Brakerski-Gentry-Vaikuntanathan (BGV) qui:

-- Code le message dans les bits de poids faible.

-- Maintient le même niveau de bruit en réduisant le module du texte chiffré après chaque multiplication

-- Permet une multiplication homomorphe beaucoup plus rapide

Mémoire de Master 2 Recherche 66 MOUYOUME DIEUDONNE(c) UYI

CONCLUSION ET PERSPECTIVES

En résumé, notre étude visait à comparer les performances en termes de temps de calcul, de chiffrement, de déchiffrement et de multiplication matricielle homomorphe des bibliothèques SEAL, OpenFHE et PALISADE utilisant les cryptosystèmes BGV et BFV. Cette comparaison suscite un intérêt croissant dans le domaine de la cryptographie. Chacune de ces bibliothèques présente des fonctionnalités et des performances distinctes, soulignant ainsi l'importance de leur évaluation et de leur comparaison pour déterminer la solution optimale en fonction des besoins spécifiques.

Il est important de noter que les performances des bibliothèques homomorphiques lors de la multiplication matricielle dépendent de divers facteurs tels que la taille des matrices, la complexité des opérations, les paramètres cryptographiques sélectionnés et les caractéristiques matérielles du système de calcul. Par conséquent, une évaluation exhaustive et approfondie de ces bibliothèques nécessite une analyse minutieuse prenant en considération tous ces aspects.

En outre, il est probable que les bibliothèques homomorphiques continueront à évoluer et à s'amé-liorer en termes de performances et de fonctionnalités. Des recherches supplémentaires seront requises pour optimiser les cryptosystèmes cryptographiques, les algorithmes de calcul et les implémentations logicielles afin de rendre les opérations homomorphes plus rapides et plus efficaces. La mise en oeuvre de solutions de chiffrement homomorphe est complexe et exige une compréhension approfondie des principes mathématiques sous-jacents.

Étant donné l'importance croissante de la confidentialité des données et de la protection de la vie privée, les bibliothèques homomorphiques pourraient jouer un rôle essentiel dans des domaines tels que l'apprentissage automatique sécurisé, l'analyse de données sensibles et la collaboration sécurisée entre différentes entités. Ces développements soulignent la nécessité continue d'innover et de perfectionner les techniques de chiffrement homomorphe pour répondre aux besoins croissants en matière de sécurité et de confidentialité des données.

En perspectives, nous comptons intégrer d'autres bibliothèques FHE dans la comparison à l'instar de HElib, utiliser des modules des textes chiffrés plus grands (16384 et 32768) et des modules de textes en clairs plus grands (786433 et 1032193).

Mémoire de Master 2 Recherche 67 MOUYOUME DIEUDONNE(c) UYI

Bibliographie

[1] Lattigo v5, howpublished = Online : https://github.com/tuneinsight/lattigo, month = nov, year = 2023, note = "[epfl-lds, tune insight sa]".

[2] Abbas Acar, Hidayet Aksu, A Selcuk Uluagac, and Mauro Conti. A survey on homomorphic encryption schemes : Theory and implementation. ACM Computing Surveys (Csur), 51(4) :1- 35, 2018.

[3] Carlos Aguilar Melchor, Marc-Olivier Kilijian, Cédric Lefebvre, and Thomas Ricosset. A comparison of the homomorphic encryption libraries helib, seal and fv-nfllib. In Innovative Security Solutions for Information Technology and Communications: 11th International Conference, SecITC 2018, Bucharest, Romania, November 8-9, 2018, Revised Selected Papers 11, pages 425-442. Springer, 2019.

[4] Jawad Ahmad, Baraq Ghaleb, Sana Ullah Jan, William J Buchanan, et al. Cross-platform benchmarking of the fhe libraries : Novel insights into seal and openfhe. arXiv preprint arXiv :2503.11216, 2025.

[5] Miklós Ajtai. Generating hard instances of lattice problems. In Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, pages 99-108, 1996.

[6] Martin Albrecht, Melissa Chase, Hao Chen, Jintai Ding, Shafi Goldwasser, Sergey Gorbunov, Shai Halevi, Jeffrey Hoffstein, Kim Laine, Kristin Lauter, Satya Lokam, Daniele Micciancio, Dustin Moody, Travis Morrison, Amit Sahai, and Vinod Vaikuntanathan. Homomorphic encryption security standard. Technical report, HomomorphicEncryption.org, Toronto, Canada, November 2018.

[7] Aldrich Ellis C Asuncion, Brian Christopher T Guadalupe, and William Emmanuel S Yu. Implementation and analysis of homomorphic facial image encryption and manipulation. In Proceedings of the 2019 4th international conference on multimedia systems and signal processing, pages 158-166, 2019.

[8] Ahmad Al Badawi, Jack Bates, Flavio Bergamaschi, David Bruce Cousins, Saroja Erabelli, Nicholas Genise, Shai Halevi, Hamish Hunt, Andrey Kim, Yongwoo Lee, Zeyu Liu, Daniele Mic-ciancio, Ian Quah, Yuriy Polyakov, Saraswathy R.V., Kurt Rohloff, Jonathan Saylor, Dmitriy Suponitsky, Matthew Triplett, Vinod Vaikuntanathan, and Vincent Zucca. Openfhe : Open-

BIBLIOGRAPHIE 68

Mémoire de Master 2 Recherche 68 MOUYOUME DIEUDONNE(c) UYI

source fully homomorphic encryption library. Cryptology ePrint Archive, Paper 2022/915, 2022. https://eprint.iacr.org/2022/915.

[9] Ahmad Al Badawi, Jack Bates, Flavio Bergamaschi, David Bruce Cousins, Saroja Erabelli, Nicholas Genise, Shai Halevi, Hamish Hunt, Andrey Kim, Yongwoo Lee, Zeyu Liu, Daniele Mic-ciancio, Ian Quah, Yuriy Polyakov, Saraswathy R.V., Kurt Rohloff, Jonathan Saylor, Dmitriy Suponitsky, Matthew Triplett, Vinod Vaikuntanathan, and Vincent Zucca. Openfhe : Open-source fully homomorphic encryption library. Cryptology ePrint Archive, Paper 2022/915, 2022. https://eprint.iacr.org/2022/915.

[10] Ayoub Benaissa, Bilal Retiat, Bogdan Cebere, and Alaa Eddine Belfedhal. Tenseal : A library for encrypted tensor operations using homomorphic encryption, 2021.

[11] Safouane Benelkadi. Etude de performance du crypto-système homomorphe sur le calcul matriciel. PhD thesis, Institut d'informatique d'Auvergne-Université Clermont Auvergne, 2020.

[12] Avrim Blum, Merrick Furst, Michael Kearns, and Richard J Lipton. Cryptographic primitives based on hard learning problems. In Annual International Cryptology Conference, pages 278- 291. Springer, 1993.

[13] Fabian Boemer, Sejun Kim, Gelila Seifu, Fillipe DM de Souza, Vinodh Gopal, et al. Intel HEXL (release 1.2). https://github.com/intel/hexl, 09 2021.

[14] Nassim Boulechfar and Aimad Chabounia. Conception et implémentation d'un compilateur de chiffrement homomorphe. Master's thesis, École nationale Supérieure d'Informatique, 06 2023.

[15] Zvika Brakerski. Fully homomorphic encryption without modulus switching from classical gapsvp. In Annual Cryptology Conference, pages 868-886. Springer, 2012.

[16] Zvika Brakerski and Vinod Vaikuntanathan. Efficient fully homomorphic encryption from (standard) lwe. SIAM Journal on computing, 43(2) :831-871, 2014.

[17] Jung Hee Cheon, Anamaria Costache, Radames Cruz Moreno, Wei Dai, Nicolas Gama, Mariya Georgieva, Shai Halevi, Miran Kim, Sunwoong Kim, Kim Laine, et al. Introduction to homo-morphic encryption and schemes. Protecting Privacy through Homomorphic Encryption, pages 3-28, 2021.

[18] Jung Hee Cheon, Andrey Kim, Miran Kim, and Yongsoo Song. Homomorphic encryption for arithmetic of approximate numbers. In Advances in Cryptology-ASIACRYPT 2017 : 23rd International Conference on the Theory and Applications of Cryptology and Information Security, Hong Kong, China, December 3-7, 2017, Proceedings, Part I 23, pages 409-437. Springer, 2017.

[19] Ilaria Chillotti, Nicolas Gama, Mariya Georgieva, and Malika Izabachène. TFHE : Fast fully homomorphic encryption library, August 2016. https :// tfhe.github.io/tfhe/.

[20] Wild code school. https://www.wildcodeschool.com/fr-fr/blog/
cest-quoi-une-librairie-en-programmation, 2023. [Page consultée le 19-Mai-2024].

[21] The PALISADE community. Palisade homomorphic encryption software library, 2021. [En ligne; Page disponible le 19-juin-2024].

[22]

BIBLIOGRAPHIE 69

Mémoire de Master 2 Recherche 69 MOUYOUME DIEUDONNE(c) UYI

Eric Crockett and Chris Peikert. ë ? ë : Functional lattice cryptography. Cryptology ePrint Archive, Paper 2015/1134, 2015.

[23] Quarkslab CryptoExperts, INP ENSEEIHT. https://github.com/quarkslab/NFLlib, 2016. [Lien consulté le 10-Mai-2025].

[24] Thi Van Thao Doan, Mohamed-Lamine Messai, Gérald Gavin, and Jérôme Darmont. A survey on implementations of homomorphic encryption schemes. The Journal of Supercomputing, pages 1-42, 2023.

[25] Leo Ducas and Daniele Micciancio. https://github.com/lducas/FHEW, 2017. [Lien consulté le 10-Mai-2025].

[26] Taher ElGamal. A public key cryptosystem and a signature scheme based on discrete logarithms. IEEE transactions on information theory, 31(4) :469-472, 1985.

[27] Saroja Erabelli. pyFHE-a Python library for fully homomorphic encryption. PhD thesis, Massachusetts Institute of Technology, 2020.

[28] Junfeng Fan and Frederik Vercauteren. Somewhat practical fully homomorphic encryption. Cryptology ePrint Archive, 2012.

[29] Shereen Mohamed Fawaz, Nahla Belal, Adel ElRefaey, and Mohamed Waleed Fakhr. A comparative study of homomorphic encryption schemes using microsoft seal. In Journal of Physics: Conference Series, volume 2128, page 012021. IOP Publishing, 2021.

[30] Cyrielle Feron. PAnTHErS : un outil d'aide pour l'analyse et l'exploration d'algorithmes de chiffrement homomorphe. PhD thesis, Brest, École nationale supérieure de techniques avancées Bretagne, 2018.

[31] Wei Dai from the Vernam Group. https://github.com/vernamlab/cuHE, 2016. [Lien consulté le 10-Mai-2025].

[32] Craig Gentry. A fully homomorphic encryption scheme. Stanford university, 2009.

[33] Craig Gentry, Amit Sahai, and Brent Waters. Homomorphic encryption from learning with errors : Conceptually-simpler, asymptotically-faster, attribute-based. In Advances in Cryptology- CRYPTO 2013 : 33rd Annual Cryptology Conference, Santa Barbara, CA, USA, August 18-22, 2013. Proceedings, Part I, pages 75-92. Springer, 2013.

[34] Mariya Georgieva. Analyse probabiliste de la réduction des réseaux euclidiens cryptographiques. PhD thesis, Université de Caen, 2013.

[35] Shai Halevi and Victor Shoup. Algorithms in helib. In Advances in Cryptology-CRYPTO 2014 : 34th Annual Cryptology Conference, Santa Barbara, CA, USA, August 17-21, 2014, Proceedings, Part I 34, pages 554-571. Springer, 2014.

[36] Andrey Kim, Yuriy Polyakov, and Vincent Zucca. Revisiting homomorphic encryption schemes for finite fields. In Advances in Cryptology-ASIACRYPT 2021 : 27th International Conference on the Theory and Application of Cryptology and Information Security, Singapore, December 6-10, 2021, Proceedings, Part III 27, pages 608-639. Springer, 2021.

[37]

BIBLIOGRAPHIE 70

Amina Bel Korchi. Déploiement de la cryptographie homomorphe dans le cadre de l'iot. PhD thesis, Université de Lyon, 2019.

[38] Kim Laine. Simple encrypted arithmetic library 2.3. 1. Microsoft Research https ://www. micro-soft. com/en-us/research/uploads/prod/2017/11/sealmanual-2-3-1. pdf, 2017.

[39] LePont. https://www.lepont-learning.com/fr/chiffrement-homomorphe-definition-avanta 2024. [Page consultée le 10-Juin-2024].

[40] Jianwei Li and Phong Q Nguyen. A complete analysis of the bkz lattice reduction algorithm (2020).

[41] Vincent Migliore, Guillaume Bonnoron, and Caroline Fontaine. Determination and exploration of practical parameters for the latest Somewhat Homomorphic Encryption (SHE) Schemes. working paper or preprint, October 2016.

[42] Abderrahmane Nitaj. L'algorithme lll et ses applications en cryptographie. 2014.

[43] Pascal Paillier. Public-key cryptosystems based on composite degree residuosity classes. In International conference on the theory and applications of cryptographic techniques, pages 223- 238. Springer, 1999.

[44] Oded Regev. On lattices, learning with errors, random linear codes, and cryptography. Journal of the ACM (JACM), 56(6) :1-40, 2009.

[45] Ronald L Rivest, Adi Shamir, and Leonard Adleman. A method for obtaining digital signatures and public-key cryptosystems. Communications of the ACM, 21(2) :120-126, 1978.

[46] Kazue Sako. GOLDWASSER-MICALI ENCRYPTION SCHEME, pages 241-242. Springer US, Boston, MA, 2005.

[47] Microsoft SEAL (release 4.1). https://github.com/Microsoft/SEAL, January 2023. Microsoft Research, Redmond, WA.

[48] Vasily Sidorov, Ethan Yi Fan Wei, and Wee Keong Ng. Comprehensive performance analysis of homomorphic cryptosystems for practical data processing. arXiv preprint arXiv :2202.02960, 2022.

[49] Rebecca Slayton, editor. Democratizing Cryptography: The Work of Whitfield Diffie and Martin Hellman, volume 42. Association for Computing Machinery, New York, NY, USA, 1 edition, 2022.

[50] Damien Stehlé, Ron Steinfeld, Keisuke Tanaka, and Keita Xagawa. Efficient public key encryption based on ideal lattices. In International Conference on the Theory and Application of Cryptology and Information Security, pages 617-635. Springer, 2009.

[51] Dr Mark van Rijmenam. https://www.thedigitalspeaker.com/author/
mark-van-rijmenam/. [Page consultée le 12-Mai-2025].

[52] Wikipédia. https://www.techno-science.net/definition/147@.html#_note-@,
2023. [Page consultée le 19-Mai-2024].

Mémoire de Master 2 Recherche 70 MOUYOUME DIEUDONNE(c) UYI

[53]

BIBLIOGRAPHIE 71

Mémoire de Master 2 Recherche 71 MOUYOUME DIEUDONNE(c) UYI

Wencheng Yang, Song Wang, Kan Yu, James Jin Kang, and Michael N. Johnstone. Secure fingerprint authentication with homomorphic encryption. In Digital Image Computing: Techniques and Applications, DICTA 2020, Melbourne, Australia, November 29 - December 2, 2020, pages 1-6. IEEE, 2020.

[54] Zama. Concrete : TFHE Compiler that converts python programs into FHE equivalent, 2022. https://github.com/zama-ai/concrete.