Modélisations de l'algorithme LLL par des systèmes

Modelisations de l’algorithme LLL par des systemes dynamiques

analyses probabilistes des modeles

Loıck Lhote

GREYC, ENSICAEN, CNRS-UMR 6072

Rencontres ALEA 2015

Marseille, mars 2015

L. Lhote (GREYC) ALEA 2015 1 / 25

1 Introduction

Reduction des reseaux

2 Algorithme LLL

3 Modelisations de l’algorithme LLL et de ses entrees

Modeles d’execution (part 1)

Modeles d’entree

4 Resultats obtenus dans les differents modeles

Modele M2 : systeme dynamique de Rd

Modele M3 : systemes dynamiques probabilistes de Rd

Experiences

5 Conclusion

Introduction

Generalisations de l’algorithme d’Euclide

Algorithmes LLL, HKZ, BKZ,

Modelisation des algorithmes

(tas de sable, CFG, etc.)

Modelisation des entrees

La modelisation des algorithmes

conduit a de nouveaux systemes dy-

namiques

Approximation Rationnelle Simultanee

Probleme :

Etant donne −→y ∈ Rn, trouver q ∈ Z avec q ≤ M et−→p ∈ Zn tels que ||q · −→y −−→p || est petit.

Developpement en fractions continues

mp−1 +1

mp + 0

Introduction

namiques

Probleme :

mp−1 +1

mp + 0

Introduction

namiques

Probleme :

mp−1 +1

mp + 0

Introduction Reduction des reseaux

Reseaux euclidiens

Un reseau euclidien de Rn est un sous-groupe discret de Rn.

Si B := (b1,b2, . . . ,bd) est un systeme de d vecteurs lineairement independants de Rn,

le reseau engendre par B est

L := {x ∈ Rn; x =

d∑i=1

xibi, xi ∈ Z}

Le systeme B := (b1,b2, . . . ,bd) est une base du reseau Ld : dimension du reseau.

Reseaux euclidiens

Un reseau possede

une infinite de basesProbleme essentiel :Trouver une “bonne base” du reseau L

avec des vecteurs assez courts et assez orthogonaux

a partir d’une base quelconque de L.

[Probleme SVP]

Peut-on trouver une base contenant un plus court

vecteur non nul du reseau ?

But de la reduction : trouver en un temps “raisonnable” une “assez bonne” base.

L’algorithme LLL concu en 1982 par A. Lenstra, H. Lenstra et L. Lovasz

trouve en temps polynomial une assez bonne base d’un reseau.

pour d = 2 : l’algorithme de Gauss trouve la meilleure base

pour d ≥ 3 : l’algorithme LLL generalise l’algorithme de Gauss

Reseaux euclidiens

Un reseau possede

une infinite de basesProbleme essentiel :Trouver une “bonne base” du reseau L

avec des vecteurs assez courts et assez orthogonaux

a partir d’une base quelconque de L.

[Probleme SVP]

Peut-on trouver une base contenant un plus court

vecteur non nul du reseau ?

But de la reduction : trouver en un temps “raisonnable” une “assez bonne” base.

L’algorithme LLL concu en 1982 par A. Lenstra, H. Lenstra et L. Lovasz

trouve en temps polynomial une assez bonne base d’un reseau.

pour d = 2 : l’algorithme de Gauss trouve la meilleure base

pour d ≥ 3 : l’algorithme LLL generalise l’algorithme de Gauss

Reduction des reseaux et analyses en moyenne

Analyses probabilistes

H. Daude, P. Flajolet, B. Vallee (annees 90) : analyse en moyenne du nombre

d’iterations de l’algorithme de Gauss (dimension 2)

A. Akhavi, J.F. Marckert, A. Rouault (2007) : un reseau uniforme dans la boule est

deja quasiment reduit

B. Vallee, A. Vera (2008,2010) : analyses en moyenne d’autres parametres de

l’algorithme de Gauss

Reduction des reseaux et modeles

Modelisations connues

M. Madritsch, B. Vallee (2010) : modelisation de l’algorithme LLL avec des tas desable

phenomenes observes dans l’algorithme LLL et prouves dans le modele de tas de sable

modele M1 dans la suite de l’expose

G. Hanrot, X. Pujol, D. Stehle (2011) : modelisation de BKZ avec un point de vue

tas de sable

M. Georgieva (these, 2013) :

modelisations des reseaux euclidiens issus de la cryptographie

autres modeles d’execution de l’algorithme LLL

Algorithme LLL

Principes de l’algorithme

L’algorithme LLL ne fait que des translations et des echanges entre deux vecteurs successifs.

Les translations :

- elles diminuent la norme des vecteurs

- on translate bi+1//bi de maniere a reduire au maximum bi+1

Les echanges :

- ils rendent la base plus orthogonale.

- Si B = (b1, . . . ,bd) est la base,

B? = (b?1, . . . ,b?d) est la base des orthogonalises de Gram-Schmidt.

- Plus les rapports ||b?i+1||/||b?i || sont grands, plus la base B est orthogonale

Algorithme LLL

Les translations :

Les echanges :

Algorithme LLL

Les translations :

Les echanges :

Algorithme LLL

Les translations :

Les echanges :

Algorithme LLL

Les translations :

Les echanges :

Algorithme LLL

Algorithme LLL(t), t ≥ 1

Entrees: B = (b1, . . . ,bd)

Resultat: B = (b1, . . . , bd) t-reduite.

Calculer la base orthogonale B?

Faire les translations utiles

tant que L(t) non satisfaite faireChoisir i tel que L(t, i) non satisfaite

Echanger bi et bi+1

Mettre a jour B?

Faire les translations utilesfin

On note M = (mi,j)i,j la matrice de passage de

B a B?

Condition de Lovasz L(t) : pour tout indice i,

L(t, i) :||b?i+1||2

||b?i ||2≥ 1

t2−m2

translations ⇒ |mi,j | ≤ 12

(base propre)

Une base B d’un reseau L qui est propre est

dite reduite au sens de t- Lovasz si elle verifie

la condition L(t)

Apres un echange, il faut revenir en arriere

pour verifier si la condition de Lovasz est

toujours valide

La strategie classique de LLL consiste a

prendre la premiere base locale non reduite

Algorithme LLL

Entrees: B = (b1, . . . ,bd)

Echanger bi et bi+1

Mettre a jour B?

B a B?

L(t, i) :||b?i+1||2

||b?i ||2≥ 1

t2−m2

(base propre)

la condition L(t)

toujours valide

Algorithme LLL

Entrees: B = (b1, . . . ,bd)

Echanger bi et bi+1

Mettre a jour B?

B a B?

L(t, i) :||b?i+1||2

||b?i ||2≥ 1

t2−m2

(base propre)

la condition L(t)

toujours valide

Algorithme LLL

Entrees: B = (b1, . . . ,bd)

Echanger bi et bi+1

Mettre a jour B?

B a B?

L(t, i) :||b?i+1||2

||b?i ||2≥ 1

t2−m2

(base propre)

la condition L(t)

toujours valide

Algorithme LLL

Entrees: B = (b1, . . . ,bd)

Echanger bi et bi+1

Mettre a jour B?

B a B?

L(t, i) :||b?i+1||2

||b?i ||2≥ 1

t2−m2

(base propre)

la condition L(t)

toujours valide

Algorithme LLL

Les echanges rendent la base plus orthogonale

`i := ‖b?i ‖, ri :=`i+1

`i(rapports de Siegel) et νi := {mi+1,i}

(partie fractionnelle centree)

Si la condition de Lovasz n’est pas verifiee entre bi et bi+1,

un echange modifie les rapports de Siegel.

multiplicatif

Les nouveaux rapports de Siegel :

ri−1 = ρ.ri−1

ρ2.ri

ri+1 = ρ.ri+1.

Algorithme LLL

`i := ‖b?i ‖, ri :=`i+1

multiplicatif

ri−1 = ρ.ri−1

ρ2.ri

ri+1 = ρ.ri+1.

avec un facteur de decroissance ρ

ρ2 = r2i + ν2i ≤1

t≤ 1

Algorithme LLL

`i := ‖b?i ‖, ri :=`i+1

multiplicatif

ri−1 = ρ.ri−1

ρ2.ri

ri+1 = ρ.ri+1.

Point de vue additif :

ci = − log ri, α = − log ρ

ci−1 = ci−1 + α

ci = ci−1 − 2α

ci+1 = ci−1 + α.

avec un facteur de decroissance ρ

ρ2 = r2i + ν2i ≤1

t≤ 1

Algorithme LLL

1 Introduction

2 Algorithme LLL

Modeles d’entree

Experiences

5 Conclusion

Modelisations de l’algorithme LLL et de ses entrees Modeles d’execution (part 1)

Notre approche :

le role essentiel est joue par les rapports

ri =`i+1

`iles coefficients νi ont un role secondaire

si ri trop petit alors

T(i)ρ (r) =

ri−1 := ρ.ri−1;

ri :=1

ρ2.ri;

ri+1 := ρ.ri+1;

Point de vue additif :

c := (c1, . . . , cd−1)

avec ci = − log ri et α = − log ρ

si ci trop grand alors

T(i)α (c) =

ci−1 := ci−1 + α

ci := ci − 2α

ci+1 := ci+1 + α

−→

Entrees: r = (r1, . . . , rd−1)

Sorties: r = (r1, . . . , rd−1) tous assez

grands

tant que r non entierement reduit

faireChoisir i tel que ri trop

petit;

Choisir ρ ∈ R+;

r← T(i)ρ (r);

Renvoyer r

Deux principaux choix :

Choisir i : la strategie

classique, gloutonne, aleatoire...

Choisir ρ : calcule, fixe...

ρi =√r2i + ν2i

M1 : ρi = ρ est constant (tas de sable)

M2 : ρi est fonction de ri, νi fixe dans [− 12, 12]

M3 : ρi est fonction de ri, νi ∈R [− 12, 12]

M4 : LLL avec la condition de Siegel (r2i ≥ 1t2− 1

M5 : vrai LLL avec la condition de Lovasz

r2i ≥ 1t2− ν2i

Entrees: r = (r1, . . . , rd−1)

grands

petit;

Choisir ρ ∈ R+;

r← T(i)ρ (r);

Renvoyer r

ρi =√r2i + ν2i

r2i ≥ 1t2− ν2i

Entrees: r = (r1, . . . , rd−1)

grands

petit;

Choisir ρ ∈ R+;

r← T(i)ρ (r);

Renvoyer r

ρi =√r2i + ν2i

r2i ≥ 1t2− ν2i

Entrees: r = (r1, . . . , rd−1)

grands

petit;

Choisir ρ ∈ R+;

r← T(i)ρ (r);

Renvoyer r

ρi =√r2i + ν2i

r2i ≥ 1t2− ν2i

Entrees: r = (r1, . . . , rd−1)

grands

petit;

Choisir ρ ∈ R+;

r← T(i)ρ (r);

Renvoyer r

ρi =√r2i + ν2i

r2i ≥ 1t2− ν2i

Entrees: r = (r1, . . . , rd−1)

grands

petit;

Choisir ρ ∈ R+;

r← T(i)ρ (r);

Renvoyer r

ρi =√r2i + ν2i

r2i ≥ 1t2− ν2i

Modelisations de l’algorithme LLL et de ses entrees Modeles d’entree

1 Introduction

2 Algorithme LLL

Modeles d’entree

Experiences

5 Conclusion

Approche generale

`1 0 · · · 0

∗ `2. . .

......

. . .. . . 0

∗ · · · ∗ `d

La longueur des orthogonalises se

lit sur la diagonale

Ainsi, on peut regler tous les pa-

rametres souhaites.

Approche generale

`1 0 · · · 0

∗ `2. . .

......

. . .. . . 0

∗ · · · ∗ `d

rametres souhaites.

Reseaux de Ajtai : A

Approche generale

`1 0 · · · 0

∗ `2. . .

......

. . .. . . 0

∗ · · · ∗ `d

rametres souhaites.

Reseaux uni-tas (NTRU) : N

Approche generale

`1 0 · · · 0

∗ `2. . .

......

. . .. . . 0

∗ · · · ∗ `d

rametres souhaites.

Reseaux uni-tas (NTRU) : N

Reseaux uni-tas (Knapsack) : K

Resultats obtenus dans les differents modeles

1 Introduction

2 Algorithme LLL

Modeles d’entree

Experiences

5 Conclusion

Resultats obtenus dans les differents modeles Modele M2 : systeme dynamique de Rd

Modele M2 : systemes dynamiques de Rd−1

ρ =√r2i + ν2i est fonction de ri mais νi est suppose constant dans [− 1

2, 12]

On pose :

xi := r2i =`2i+1

`2i← variable, xi := r2i =

ˇ2i+1

, µ := ν2i ← constant

Le facteur de decroissance : ρ =√xi + µ

Si r2i <1

t2− µ

ri−1 = ρri−1

ri+1 = ρri+1.

M2(t, µ)

Si xi <1

t2− µ

xi−1 = xi−1(xi + µ)

xi =xi

(xi + µ)2

xi+1 = xi+1(xi + µ)

M2(t, µ) modelise et analyse l’algorithme LLL(t) (egalement pour t = 1)

Le trou du systeme M2(t, µ) (condition d’arret) est (x1, . . . , xd−1) ∈[

1t2− µ,+∞

[d−1.

2, 12]

On pose :

xi := r2i =`2i+1

ˇ2i+1

Si r2i <1

t2− µ

ri−1 = ρri−1

ri+1 = ρri+1.

M2(t, µ)

Si xi <1

t2− µ

xi−1 = xi−1(xi + µ)

xi =xi

(xi + µ)2

xi+1 = xi+1(xi + µ)

1t2− µ,+∞

[d−1.

2, 12]

On pose :

xi := r2i =`2i+1

ˇ2i+1

Si r2i <1

t2− µ

ri−1 = ρri−1

ri+1 = ρri+1.

M2(t, µ)

Si xi <1

t2− µ

xi−1 = xi−1(xi + µ)

xi =xi

(xi + µ)2

xi+1 = xi+1(xi + µ)

1t2− µ,+∞

[d−1.

2, 12]

On pose :

xi := r2i =`2i+1

ˇ2i+1

Si r2i <1

t2− µ

ri−1 = ρri−1

ri+1 = ρri+1.

M2(t, µ)

Si xi <1

t2− µ

xi−1 = xi−1(xi + µ)

xi =xi

(xi + µ)2

xi+1 = xi+1(xi + µ)

1t2− µ,+∞

[d−1.

2, 12]

On pose :

xi := r2i =`2i+1

ˇ2i+1

Si r2i <1

t2− µ

ri−1 = ρri−1

ri+1 = ρri+1.

M2(t, µ)

Si xi <1

t2− µ

xi−1 = xi−1(xi + µ)

xi =xi

(xi + µ)2

xi+1 = xi+1(xi + µ)

1t2− µ,+∞

[d−1.

Etude du modele M2

M2 n’est plus un tas de sable : c’est un systeme dynamique general, “a trou”

Nous avons analyse ce modele :

avec la strategie gloutonne : on reduit la ou ri est le plus faible (ci est le plus grand)

en dimension 2 : pour t ≥ 1

des resultats similaires a ceux connus sur l’algorithme de Gauss

une distribution geometrique pour le nombre d’iterations

en dimension 3 : (le premier cas ou l’algorithme LLL(t) n’est pas bien connu)

pour t ≥ 1 : le nombre d’etapes suit toujours une loi geometrique

sauf pour des densites particulieres

en dimension d :

pour t > 1 : l’asymptotique du nombre d’iterations du modele M2(t, µ),

ce resultat n’etant pas connu pour LLL(t)

le passage entre LLL(t) et LLL(1) est conjecture.

Etude du modele M2

en dimension d :

Etude du modele M2

en dimension d :

Etude du modele M2

en dimension d :

Etude du modele M2

en dimension d :

Υ = log∏

ri (controle avec le modele des entrees)

Modeles K pire des cas K pour M1(α) K pour M2(µ) K exp.

A(Υ, d)

12 log td(d+ 1)Υ

12αd(d+ 1)Υ

6| log µ|d(d+ 1)Υ

Θ(d2Υ)

N (Υ, d)

8 log td2Υ

8αd2Υ

4| log µ|d2Υ

Θ(d2Υ)

K(Υ, d)

2 log tdΥ

2αdΥ

| log µ|dΥ

Θ(dΥ)

A=Ajtaı (grands-tas), N=NTRU (uni-tas au milieu),

K=Sac-a-dos (uni-tas au debut)

Υ = log∏

A(Υ, d)1

12 log td(d+ 1)Υ

12αd(d+ 1)Υ

6| log µ|d(d+ 1)Υ

Θ(d2Υ)

N (Υ, d)1

8 log td2Υ

8αd2Υ

4| log µ|d2Υ

Θ(d2Υ)

K(Υ, d)1

2 log tdΥ

2αdΥ

| log µ|dΥ

Θ(dΥ)

Υ = log∏

A(Υ, d)1

12 log td(d+ 1)Υ

12αd(d+ 1)Υ

6| log µ|d(d+ 1)Υ

Θ(d2Υ)

N (Υ, d)1

8 log td2Υ

8αd2Υ

4| log µ|d2Υ

Θ(d2Υ)

K(Υ, d)1

2 log tdΥ

2αdΥ

| log µ|dΥ

Θ(dΥ)

Υ = log∏

A(Υ, d)1

12 log td(d+ 1)Υ

12αd(d+ 1)Υ

6| log µ|d(d+ 1)Υ Θ(d2Υ)

N (Υ, d)1

8 log td2Υ

8αd2Υ

4| log µ|d2Υ Θ(d2Υ)

K(Υ, d)1

2 log tdΥ

2αdΥ

| log µ|dΥ Θ(dΥ)

Resultats obtenus dans les differents modeles Modele M3 : systemes dynamiques probabilistes de Rd

Modele M3 : systemes dynamiques probabilistes

ρ est fonction de ri, νi est uniforme dans [− 12, 12]

On pose :

xi := r2i =`2i+1

ˇ2i+1

, µi := ν2i avec νi ∈R [−1

Si xi <1

t2− µi

xi−1 = xi−1(xi + µi)

xi =xi

(xi + µi)2

xi+1 = xi+1(xi + µi)

Generer un nouveau µi

C’est un systeme dynamique probabiliste dans

Rd−1, a trou, chaque transformation ayant un point

fixe attractif

Aucun resultat !

Modele M3 : systemes dynamiques probabilistes

ρ est fonction de ri, νi est uniforme dans [− 12, 12]

On pose :

xi := r2i =`2i+1

ˇ2i+1

, µi := ν2i avec νi ∈R [−1

Si xi <1

t2− µi

xi−1 = xi−1(xi + µi)

xi =xi

(xi + µi)2

xi+1 = xi+1(xi + µi)

Generer un nouveau µi

C’est un systeme dynamique probabiliste dans

Rd−1, a trou, chaque transformation ayant un point

fixe attractif

Aucun resultat !

Conjecture d’un resultat

Potentiel : ∆(x) =

d∏i=1

xi(d−i)i

L’argument principal pour l’asymptotique du modele M2 est :

∆(x) =∆(x)

mini(xi + µ)∼ ∆(x)

Par recurrence (xi =configuration apres i etapes)

∆(xi) ∼∆(x0)

Conjecture :

On note µ[i] le coefficient sous-diagonal intervenant a la i-eme etape de LLL. Alors

∆(xi) ∼ ∆(x0)i∏

d∏i=1

xi(d−i)i

∆(x) =∆(x)

∆(xi) ∼∆(x0)

Conjecture :

∆(xi) ∼ ∆(x0)i∏

d∏i=1

xi(d−i)i

∆(x) =∆(x)

∆(xi) ∼∆(x0)

Conjecture :

∆(xi) ∼ ∆(x0)i∏

Resultats obtenus dans les differents modeles Experiences

Conjecture et LLL glouton (dimension 3)

0 50 100 150 200 250 300 350 400 450

temps (1 unite = 1 echange)

LLL-max(1):potentiel- dim=3, ri=(1/2)**500

reelleestimee

0 200 400 600 800 1000 1200 1400 1600 1800 2000

reelleestimee

la conjecture + un bon modele pour les νi

+ une analyse du modele M3(t)

= une bonne comprehension de LLL(t)

0 200 400 600 800 1000 1200 1400 1600 1800 2000

reelleestimee

la conjecture + un bon modele pour les νi

+ une analyse du modele M3(t)

= une bonne comprehension de LLL(t)

Conclusion

Une classe de modeles simplifies pour l’execution de l’algorithme :

du plus simple (cfg) au plus complique (l’algorithme LLL)

Etude d’un modele semi-simplifie d’execution :

une analyse totale pour d = 3

ou l’analyse du veritable algorithme LLL est deja mal comprise

analyse partielle en dimension generale.

Modelisation des familles de reseaux cryptographiques, dans le cadre d’un cfg

Modelisation d’autres algorithmes de reduction de reseaux (DeepLLL)

Pour le modele M2, prouver la conjecture, qui permettrait d’avoir un modele simplifie

pour l’algorithme LLL associe au parametre t = 1

Analyser le modele M3

Modele de l’evolution du coefficient sous diagonal

Conclusion

Merci pour votre attention !

Modélisations de l'algorithme LLL par des systèmes

Documents

Résultats des modélisations - Loire-Atlantique · STELIA AEROSPACE – Site de Saint-Nazaire (44) Résultats des modélisations Projet N° 46314833 25 septembre 2014 Référence

CRDS LLL · CRDS LLL communiquera pour les rendez-vous en cabinet (agente administrative, secrétaire médicale, infirmière, etc.) ... Gestion d’infections récidivantes à germes

A MMM III CCC AAA LLL EEE 22001188 B OOO I UU LLL II T SSS

Détection et diagnostic par combinaison d'un banc de filtres et de l'algorithme séquentiel DCS

Gestion et appui aux opérations - UNHCR...GESTION ET APPUI AUX OPÉRATIONS lll lll. Appel global 2017 du HCR - actualisation87 Budgets pour le siège 2008-2017 | en millions d’USD

Modélisations des réseaux de télécommunications

L'ALGORITHME - Cours et formations - Télécharger PDFmcours.net/cours/pdf/info/apprendre_la... · L'ALGORITHME Préambule : le Codage 8 ... 12.2 Interprétation et compilation 244

Modélisations graphiques d’un plan de nivellement ...thierry.hatt.gps.free.fr/01-site-acad-tous-pdf/Hatt-2014-plans-de... · 1 Modélisations graphiques d’un plan de nivellement

Joouurrnnaall dee lll ’’ééccoolee AAnnddrréé GGiiddee

ENS L3 : Systèmes numériques : de l'algorithme aux circuits

Gestion lll

´Etude et implémentation de l'algorithme du simplexe standard sur

Modélisations géostatistiques du faciès petrophysique du

AVULSOI CrS 0.70 • .' • ,,L rnJ lll üUlllii»-lrvIm tm 11 ...memoria.bn.br/pdf/170054/per170054_1947_14405.pdf · ,,L_rnJ lll üUlllii»-"lrvIm tm 11 I ll I lll \ «ca.¦ COMERCIO

Modélisations et analyses de réseaux de capteurs

Flot maximal par l'algorithme d'Edmonds-Karp

Validation du code de calcul GARDÉNIA par modélisations

Un exemple de l'algorithme de Little pour le problème du voyageur

DvMark DvMark · MULTIAMP FG - tête digitale pour guitare - Signature Frank Gambale. 3 canaux entièrement programmables (clean, crunch, lead) - modélisations d’amplis - modélisations

Yes - 摂南大学p-bisei/Lecture_files/Biochem-III...EF-Tu2・GTP複合体がアミノアシルtRNAをAサイトに運ぶ。 E P A UAC fMet EF-Tu2 GTP 5' 3' mRNA AUG lll lll lll