Chiffrement homomorphe

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