Chiffrement homomorphe

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]