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 :
Rp =
7Lp[X]/(Xd + 1) d
= 2k, k = 2 et p le module du texte
en clair
Rq × Rq où
Rq =
7Lq[X]/(Xd + 1) avec
d = 2k, 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
2 ?,..., ?q2?} 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) +
sk2, 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 Cd/2 en un polynôme
m(X) E Z[X]/(Xd + 1)
où d est une puissance de 2.
L'espace de texte en clair est l'anneau polynomial R =
Z[X]/(Xd + 1).
L'espace du texte chiffré est
(Z[X]/(Xd + 1))2 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
Rq, 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) ?
R2q 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.sk2, a'); a' est
éhantillonné uniformément au hasard à partir de
Rpq et e' une erreur suivant la
distribution gaussienne discète ÷.
| 
