Chiffrement homomorphe

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.