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
Rq =
7Lq[x]/(xn + 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.
| 
