1. Algorithme LLL (Lenstra-Lenstra-Lovász)
En 1982, Lenstra, Lenstra et Lovász[42] ont inventé
un algorithme très efficace pour la réduction des
réseaux ayant des dimensions supérieures. Il prend en
entrée une base quelconque (b1,. . . , bn)
et la transforme en une base presque orthogonale, en réduisant la taille
des vecteurs.
L'idée principale de l'algorithme LLL est de remplacer les
vecteurs de la base qui ne sont pas "presque orthogonaux" par des combinaisons
linéaires entières de ces vecteurs. L'algorithme s'exécute
en temps polynomial.
Algorithm 1 Réduction LLL
(Lenstra-Lenstra-Lovász)
i1 [
Entrée : Base B =
{b1, . . . , bn} ?
m, ä ? 4, 1
Sortie : Base LLL-réduite
Calculer la base orthogonale {u1,.. . ,
un} par Gram-Schmidt i ? 2
tant que i = n
faire
pour j = i - 1 to 1
faire
ui, j ?
?uj,uj?
bi ? bi -
?ui, j? · bj Mettre
à jour ui
?bi,uj?
si ä?ui-1?2
> ?ui +
ui,i-1ui-1?2
alors
Échanger bi et
bi-1 i ? max(i - 1,2)
sinon
i ? i + 1
Retouner : B
La complexité de l'algorithme LLL est: O(d6
log3 T) avec T = ||bi|| pour tout
i
2. Algorithme BKZ (Block Korkine-Zolotarev)
L'algorithme BKZ introduit en 1987 [40] est une
amélioration de l'algorithme LLL. Il utilise une
1.1 Notions mathématiques 15
approche en blocs pour obtenir une réduction plus forte
des vecteurs dans le réseau euclidien. L'algo-rithme BKZ est plus
efficace que LLL pour les instances difficiles, mais il est également
plus coûteux en temps de calcul.
Algorithm 2 Réduction BKZ (Block
Korkine-Zolotarev)
Entrée : Base B =
{b1,. . . ,bn} ?
Zm, taille de bloc â = 2, paramètre ô
?]1 4, 1[ Sortie : Base
BKZ-réduite
Appliquer LLL(B, ô) sur toute la base; k
? 1
tant que k = n - 1
faire
q?min(k+â-1,n)Bbloc
?{bk,...,bq}
Bréduit ? LLL(Bbloc, ô) v
?
EnumérerVecteurMin(Bréduit)
si ?v? < ?bk?
alors
Remplacer bk par v
dans B
Appliquer LLL(B, ô) localement autour de k
k?max(k- 1,1)
sinon
Appliquer LLL(B, ô) sur
{bk,. . . , bq}
k ? k + 1
Retouner: B
La complexité de l'algorithme BKZ est
O(n2
â2 logn)
Étant donné un paramètre fixé
n = 1, un module q = 2, une distribution d'erreur X
d'écart type ó. Le problème LWE consiste à trouver
S ? Zn q à partir de m échantillons
(Ai, < Ai, S > +Ei) où les
Ai sont des vecteurs tirés uniformément de Zm q
× Zn q et les Ei sont des erreurs tirées
d'une distribution
gaussienne X sur Zn q.
Problème 1.1.10 (LWE -Apprentissage avec
erreur)
Mémoire de Master 2 Recherche 15 MOUYOUME
DIEUDONNE(c) UYI
Le problème d'apprentissage avec erreur (LWE pour
Learning With Errors) introduit en 2005 par Oded Regev [44] est un des
problèmes difficile sur lequel reposent plusieurs cryptosystèmes
à base de réseaux euclidiens. Le problème Learning with
errors (LWE) consiste à trouver un secret masqué au milieu
d'équations linéaires bruitées.
Exemple 1.1.1. Système
linéaire du problème LWE
|
???????????????????????????????
|
×
|
???????????????
|
6
9
11
11
|
???????????????
|
+
|
???????????????????????????????
|
0 -1 1 -1 1 0 -1
|
???????????????????????????????
|
=
|
???????????????????????????????
|
4
7
2
1
5
12
8
|
???????????????????????????????
|
|
???????????????????????????????
|
4 1 11 10
5 5 9 5
3 9 0 10
6 9 0 2 12 7 3 2 6 5 11 4 3 3 5 0
|
1.1 Notions mathématiques 16
Il s'agit de trouver le sécret s dans
(Z/13Z)4
Soit un entier d = 2k, k
> 2 et q un module premier tel que q 1 mod
2?(d) avec ?(d) = 2k-1. On
définit Rq =
Zq[x]/(xd + 1) un anneau de
polynôme.
Étant donné un secret S E
Rq, on construit m
échantillons (A, B) = (A,
A.S + E) E Rq X
Rq oÙ A est tiré
uniformément de Rq et E
est un terme d'erreur choisi indépendamment d'une certaine
distribution d'erreur sur Rq .
Le problème RLWE consiste à trouver S
à partir des échantillons.
Problème 1.1.11 (Ring-LWE-Apprentissage
avec erreurs sur les anneaux)
Mémoire de Master 2 Recherche 16 MOUYOUME
DIEUDONNE(c) UYI
Le problème de l'apprentissage avec erreurs sur les
anneaux (Ring-LWE pour Ring Learning With Error), introduit par Stehlé,
Steinfeld, Tanaka et Xagawa dans [50] est le problème LWE dans un anneau
de polynômes.
Mémoire de Master 2 Recherche 17 MOUYOUME DIEUDONNE(c)
UYI
| 
