44
Algorithmique de la réduction de réseaux et application à la recherche de pires cas pour l’arrondi de fonctions mathématiques Damien STEHLÉ 2 décembre 2005 http://www.loria.fr/~stehle/these.html

Algorithmique de la réduction de réseaux et application à

  • Upload
    others

  • View
    1

  • Download
    0

Embed Size (px)

Citation preview

Page 1: Algorithmique de la réduction de réseaux et application à

Algorithmique de la réduction de réseaux et application à la

recherche de pires cas pour l’arrondi de fonctions

mathématiques

Damien STEHLÉ

2 décembre 2005

http://www.loria.fr/~stehle/these.html

Page 2: Algorithmique de la réduction de réseaux et application à

Algorithmique de la réduction de réseaux et application à la recherche de pires cas pour l’arrondi de fonctions mathématiques.

Sommaire.

1. Algorithmique de la réduction des réseaux.

2. Arrondi des fonctions mathématiques.

3. Conclusion et perspectives.

02/12/2005 Damien STEHLÉ 1/43

Page 3: Algorithmique de la réduction de réseaux et application à

Algorithmique de la réduction de réseaux et application à la recherche de pires cas pour l’arrondi de fonctions mathématiques.

1) Algorithmique de la réduction de réseaux.

02/12/2005 Damien STEHLÉ 2/43

Page 4: Algorithmique de la réduction de réseaux et application à

1) Algorithmique de la réduction de réseaux.

Trois bases d’un réseau de dimension 2.

� � � � � � � � �

� � � � � � � � �

� � � � � � � � �

� � � � � � � � �

� � � � � � � � �

� � � � � � � � �

� � � � � � � � �

� � � � � � � � �

� � � � � � � � �

� � � � � � � � �

� � � � � � � � �

� � � � � � � �

� � � � � � � �

� � � � � � � �

� � � � � � � �

� � � � � � � �

� � � � � � � �

� � � � � � � �

� � � � � � � �

� � � � � � � �

� � � � � � � �

� � � � � � � �

� � � � � � � � � � � � � � � � � � �

� � � � � � � � � � � � � � � � � � �

� � � � � � � � � � � � � � � � � � �

� � � � � � � � � � � � � � � � � � �

� � � � � � � � � � � � � � � � � � �

� � � � � � � � � � � � � � � � � � �

� � � � � � � � � � � � � � � � � � �

� � � � � � � � � � � � � � � � � � �

� � � � � � � � � � � � � � � � � � �

� � � � � � � � � � � � � � � � � � �

� � � � � � � � � � � � � � � � � � �

� � � � � � � � � � � � � � � � � � �

� � � � � � � � � � � � � � � � � � �

� � � � � � � � � � � � � � � � � � �

� � � � � � � � � � � � � � � � � � �

� � � � � � � � � � � � � � � � � � �

� � � � � � � � � � � � � � � � � � �

� � � � � � � � � � � � � � � � � � �

� � � � � � � � � � � � � � � � � � �

� � � � � � � � � � � � � � � � � � �

� � � � � � � � � � � � � � � � � � �

� � � � � � � � � � � � � � � � � � �

� � � � � � � � � � � � � � � � � � �

� � � � � � � � � � � � � � � � � � �

� � � � � � � � � � � � � � � � � � �

� � � � � � � � � � � � � � � � � � �

� � � � � � � � � � � � � � � � � � �

� � � � � � � � � � � � � � � � � � �

� � � � � � � � � � � � � � � � � � �

� � � � � � � � � � � � � � � � � � �

� � � � � � � � � � � � � � � � � �

� � � � � � � � � � � � � � � � � �

� � � � � � � � � � � � � � � � � �

� � � � � � � � � � � � � � � � � �

� � � � � � � � � � � � � � � � � �

� � � � � � � � � � � � � � � � � �

� � � � � � � � � � � � � � � � � �

� � � � � � � � � � � � � � � � � �

� � � � � � � � � � � � � � � � � �

� � � � � � � � � � � � � � � � � �

� � � � � � � � � � � � � � � � � �

� � � � � � � � � � � � � � � � � �

� � � � � � � � � � � � � � � � � �

� � � � � � � � � � � � � � � � � �

� � � � � � � � � � � � � � � � � �

� � � � � � � � � � � � � � � � � �

� � � � � � � � � � � � � � � � � �

� � � � � � � � � � � � � � � � � �

� � � � � � � � � � � � � � � � � �

� � � � � � � � � � � � � � � � � �

� � � � � � � � � � � � � � � � � �

� � � � � � � � � � � � � � � � � �

� � � � � � � � � � � � � � � � � �

� � � � � � � � � � � � � � � � � �

� � � � � � � � � � � � � � � � � �

� � � � � � � � � � � � � � � � � �

� � � � � � � � � � � � � � � � � �

� � � � � � � � � � � � � � � � � �

� � � � � � � � � � � � � � � � � �

� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �

� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �

� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �

� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �

� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �

� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �

� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �

� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �

� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �

� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �

� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �

� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �

� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �

� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �

� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �

� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �

� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �

� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �

� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �

� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �

� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �

� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �

� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �

� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �

� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �

� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �

� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �

� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �

� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �

� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �

� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �

� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �

� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �

� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �

� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �

� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �

� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �

� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �

� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �

� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �

� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �

� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �

� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �

� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �

� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �

� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �

� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �

� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �

� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �

� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �

� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �

� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �

� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �

� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �

� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �

� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �

� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �

� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �

� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �

� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �

� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �

� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �

� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �

� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �

� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �

� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �

� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �

� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �

� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �

� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �

� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �

� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �

� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �

� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �

� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �

� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �

� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �

� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �

� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �

� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �

� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �

� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �

� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �

� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �

� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �

� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �

� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �

� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �

� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �

� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �

� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �

� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �

� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �

� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �

0

02/12/2005 Damien STEHLÉ 3/43

Page 5: Algorithmique de la réduction de réseaux et application à

1) Algorithmique de la réduction de réseaux.

Deux bases d’un réseau de dimension 3.

PS

fragreplacem

ents

BONNE

MAUVAISE

02/12/2005 Damien STEHLÉ 4/43

Page 6: Algorithmique de la réduction de réseaux et application à

1) Algorithmique de la réduction de réseaux.

Les réseaux euclidiens.

– Réseau : sous-groupe discret de

��

.

� ���� � �

� �

�� � � �� � � �

– Infinité de bases, liées entre elles par des relations unimodulaires.

– Leur cardinalité commune�est la dimension.

� �� � �

est représenté par la matrice

��� � d’une base quelconque.

02/12/2005 Damien STEHLÉ 5/43

Page 7: Algorithmique de la réduction de réseaux et application à

1) Algorithmique de la réduction de réseaux.

Problèmes algorithmiques.

Donnée : une base d’un réseau à coefficients entiers.

– Trouver le vecteur le plus court (SVP).

0

PSfrag replacements ���

���

– Trouver un vecteur assez court.

– Trouver une base avec des vecteurs assez courts et orthogonaux.

02/12/2005 Damien STEHLÉ 6/43

Page 8: Algorithmique de la réduction de réseaux et application à

1) Algorithmique de la réduction de réseaux.

Les réseaux euclidiens, à quoi ça sert ?

– Cryptanalyse : sac-à-dos, RSA, schémas de signature

(sous certaines conditions).

– Cryptosystèmes : NTRU, GGH, Ajtai-Dwork.

– Théorie algorithmique des nombres.

– Théorie de la complexité.

02/12/2005 Damien STEHLÉ 7/43

Page 9: Algorithmique de la réduction de réseaux et application à

1) Algorithmique de la réduction de réseaux.

Contributions.

1. Un algorithme de calcul de pgcd de complexité quasi-linéaire :

pgcd-BG-rapide.

2. Un algorithme de réduction optimale pour

� � �

, de complexité

quadratique : glouton.

3. Un algorithme de réduction en dimension quelconque : L

.

4. Des observations expérimentales sur l’algorithme L

.

02/12/2005 Damien STEHLÉ 8/43

Page 10: Algorithmique de la réduction de réseaux et application à

1) Algorithmique de la réduction de réseaux, l’algorithme glouton.

Dimension 2 : algorithme de Lagrange.

u1

v1

0

02/12/2005 Damien STEHLÉ 9/43

Page 11: Algorithmique de la réduction de réseaux et application à

1) Algorithmique de la réduction de réseaux, l’algorithme glouton.

Dimension 2 : algorithme de Lagrange.

u1

v1

0

02/12/2005 Damien STEHLÉ 10/43

Page 12: Algorithmique de la réduction de réseaux et application à

1) Algorithmique de la réduction de réseaux, l’algorithme glouton.

Dimension 2 : algorithme de Lagrange.

v2

u2

0

02/12/2005 Damien STEHLÉ 11/43

Page 13: Algorithmique de la réduction de réseaux et application à

1) Algorithmique de la réduction de réseaux, l’algorithme glouton.

Dimension 2 : algorithme de Lagrange.

v2

u2

0

02/12/2005 Damien STEHLÉ 12/43

Page 14: Algorithmique de la réduction de réseaux et application à

1) Algorithmique de la réduction de réseaux, l’algorithme glouton.

Dimension 2 : algorithme de Lagrange.

u3

v3

0

02/12/2005 Damien STEHLÉ 13/43

Page 15: Algorithmique de la réduction de réseaux et application à

1) Algorithmique de la réduction de réseaux, l’algorithme glouton.

Dimension 2 : algorithme de Lagrange.

u3

v3

0

02/12/2005 Damien STEHLÉ 14/43

Page 16: Algorithmique de la réduction de réseaux et application à

1) Algorithmique de la réduction de réseaux, l’algorithme glouton.

Dimension 2 : algorithme de Lagrange.

u4

v40

02/12/2005 Damien STEHLÉ 15/43

Page 17: Algorithmique de la réduction de réseaux et application à

1) Algorithmique de la réduction de réseaux, l’algorithme glouton.

Réduction en dimensions 2 à 4.

– Dimension 2 : algorithme de Lagrange (Gauss). Les vecteurs

renvoyés sont les deux plus courts possibles.

Complexité quadratique.

– Dimension 3 : algorithmes de Vallée et Semaev.

– Algorithme glouton : généralisation de l’algorithme de Lagrange

pour

� � �

. Il renvoie les�

vecteurs les plus courts possibles.

Complexité quadratique.

02/12/2005 Damien STEHLÉ 16/43

Page 18: Algorithmique de la réduction de réseaux et application à

1) Algorithmique de la réduction de réseaux, l’algorithme glouton.

L’algorithme glouton.

Entrée :

� � � � � � .Sortie : Une base « réduite ».

1. Ordonner les vecteurs par longueurs croissantes.

2. Réduire

� � � � � � �� � .

3. Raccourcir autant que possible� à l’aide de

� � � � � � �� � :

� � �� � � � � � � � � � � �� � � �� � � �

4. Si

� est modifié, retourner en 1.

02/12/2005 Damien STEHLÉ 17/43

Page 19: Algorithmique de la réduction de réseaux et application à

1) Algorithmique de la réduction de réseaux, l’algorithme glouton.

Analyse de l’algorithme glouton.

– Première partie : le nombre d’itérations de boucle est linéaire.

1. Approche globale : quand le produit des longueurs ne décroît

plus géométriquement, il reste

� �� �itérations de boucle.

2. Approche locale : toutes les�

itérations de boucle le produit des

longueurs décroît géométriquement.

– Seconde partie : analyse amortie pour sommer finement les coûts

des étapes successives.

02/12/2005 Damien STEHLÉ 18/43

Page 20: Algorithmique de la réduction de réseaux et application à

1) Algorithmique de la réduction de réseaux, l’algorithme L

.

État de l’art en dimension

.

– L’algorithme LLL (1982) renvoie un vecteur de norme

� � �� � ��� � � � � � . Complexité

� � � � � � � �.

– Très cher en pratique : cas de la factorisation d’un module RSA� � ��� � quand la moitié des chiffres de � sont connus :

� � � � �� � � � � � � «

� � � � � � � � �

» �

– Arithmétique rationnelle dans l’orthogonalisation sous-jacente...

02/12/2005 Damien STEHLÉ 19/43

Page 21: Algorithmique de la réduction de réseaux et application à

1) Algorithmique de la réduction de réseaux, l’algorithme L

.

État de l’art en dimension

.

– Schnorr’88 : précision des calculs

� � � � � � � � �.

Complexité

� � � � � � � � � � � � � � � �

.

– Algorithme difficile à décrire, modèle « arithmétique flottante » non

précisé, précision requise élevée. Pas implanté.

– Koy-Schnorr’01 : Givens/Householder plutôt que Gram-Schmidt.

– Schnorr’04 (non publié) : précision

� � � � � � � �

.

02/12/2005 Damien STEHLÉ 20/43

Page 22: Algorithmique de la réduction de réseaux et application à

1) Algorithmique de la réduction de réseaux, l’algorithme L

.

L’algorithme L

.

Un LLL flottant prouvé dans un modèle précis.

LLL’82 Schnorr’88 L

’05

Précision

� �� ��� � � � � � � ��� �� � � ��� �� � � ��

�� �

Complexité

� � � � ��� � � � � � � � � � � � ��� � � � � ��� � � � � � � � �� � ��� � � � ��� � � �

L

est simple à décrire. Bonne version de LLL ?

02/12/2005 Damien STEHLÉ 21/43

Page 23: Algorithmique de la réduction de réseaux et application à

1) Algorithmique de la réduction de réseaux, l’algorithme L

.

Les trois idées principales.

– Utilisation exclusive de la matrice de Gram

(pour éviter les pertes de précision liées aux produits scalaires).

– Version paresseuse de l’étape de « proprification »

(pour éviter d’utiliser plus de bits de précision qu’il n’en faut).

– Généralisation en dimension�des analyses amorties des

algorithmes d’Euclide, de Lagrange et glouton.

02/12/2005 Damien STEHLÉ 22/43

Page 24: Algorithmique de la réduction de réseaux et application à

1) Algorithmique de la réduction de réseaux, remarques expérimentales.

L’algorithme LLL en pratique.

– Bibliothèques ayant un LLL efficace : NTL, Magma, Pari GP, Lidia.

– fplll-1.2 codé en C (GNU MP, MPFR), sous GPL.

� ��� � �

NTL variante rapide variante prouvée

entrées aléatoires

�� � � � � � ��� � � � � � �

sac-à-dos

� � � � � � � � � � � �� � � �� � �

02/12/2005 Damien STEHLÉ 23/43

Page 25: Algorithmique de la réduction de réseaux et application à

1) Algorithmique de la réduction de réseaux, remarques expérimentales.

L’arithmétique flottante dans LLL.

Un réseau de dimension 55 fait boucler le LLL_FP de NTL.

2

666666666664

� �� � ��� � �

�� � �

� � �

� �

� � �� � �� � � � � �� � �

� � �

� � �

� �

� � � �� � �

� � � � � � � �� � �

� � � � � � � �� � �

� � �� � �

� �

.

.

....

.

.

.. . .

.

.

....

� � �� � �

� � � � � � � � � � �� � � � � � �� � �� � �� � �

� �� � �

� �

� � � � � �� � � � � � � � �� � � � � � � � ��� � �� � �

� � � � � � � � �� � �

� � ��� � �� �

3

777777777775

Analyse heuristique de la précision requise « en moyenne » :

53 bits devraient suffire jusqu’en dimension 180.

02/12/2005 Damien STEHLÉ 24/43

Page 26: Algorithmique de la réduction de réseaux et application à

1) Algorithmique de la réduction de réseaux, remarques expérimentales.

L’arithmétique flottante dans LLL.

Faut-il remplacer Gram-Schmidt par Givens/Householder ?

Un réseau de dimension 3 fait boucler le G_LLL_FP de NTL.

�����

� � �

� � � � � � � � � � � �

� � � � � �

� � �

�����

02/12/2005 Damien STEHLÉ 25/43

Page 27: Algorithmique de la réduction de réseaux et application à

1) Algorithmique de la réduction de réseaux, remarques expérimentales.

Autres remarques sur le comportement pratique de LLL.

– Temps d’exécution asymptotiquement conforme à la borne dans le

cas le pire, à une constante près.

– Qualité de la base renvoyée conforme à la borne dans le cas le

pire, à une constante près dans l’exposant.

0.85

0.9

0.95

1

1.05

1.1

1.15

1.2

1.25

-0.6 -0.4 -0.2 0 0.2 0.4 0.6

02/12/2005 Damien STEHLÉ 26/43

Page 28: Algorithmique de la réduction de réseaux et application à

Algorithmique de la réduction de réseaux et application à la recherche de pires cas pour l’arrondi de fonctions mathématiques.

2) Arrondi des fonctions mathématiques.

02/12/2005 Damien STEHLÉ 27/43

Page 29: Algorithmique de la réduction de réseaux et application à

2) Arrondi des fonctions mathématiques.

Rappels sur l’arithmétique flottante.

– � � � ��� � ����

, avec � � � �� � � � �

sur � bits.

– La valeur renvoyée pour « � op

» doit être la plus proche possible

de la valeur réelle exacte, pour op

� � � � � �

.

– Double précision :

bits de mantisse (IEEE-754).

– Double précision étendue :� �

bits (x87).

– Quadruple précision :

� � bits.

– Précision arbitraire : MPFR, classe RR de NTL, ...

02/12/2005 Damien STEHLÉ 28/43

Page 30: Algorithmique de la réduction de réseaux et application à

2) Arrondi des fonctions mathématiques.

Arrondi des fonctions.

– Une fonction

��� �� � � � � � � �

, transcendante,� �

, avec des

dérivées bornées : � � � � � �� � � � � � � � ��� � � � � � � �

– But : implanter

, en précision �.

� � �� � �� � � � � � � � � � � � � �� �� � � � � � � � � �� � � �

� � � �� �� � � �

� � �� � � � � � � � � � �� � � � � � � � �� � � � � �� � � � � � � � � � �

� � � � � �� � � � �

02/12/2005 Damien STEHLÉ 29/43

Page 31: Algorithmique de la réduction de réseaux et application à

2) Arrondi des fonctions mathématiques.

Pires cas pour l’arrondi.

� � � � � � � � � � � � ��

� � � � � � �

| {z }

� �

� � � � � � � � � � � � �

| {z }

� �

� �� � �

� ��

� � � � � � �

� �� �� � � � � � �� � �� �� � � ��

�� � �

| {z }� �

� �� � �

| {z }� �

� � �

� ��

�� � �

Pour un exposant donné, on s’attend à trouver les solutions

extrêmes � � �� � � � � � � ��

� � � � �� � � � �

� � � �� � �

pour :

� � � � � � � � � � � � � � � � � � ��� � � � �

02/12/2005 Damien STEHLÉ 30/43

Page 32: Algorithmique de la réduction de réseaux et application à

2) Arrondi des fonctions mathématiques.

Travaux antérieurs.

– Pires cas : Lefèvre, complexité heuristique

� � � � ���.

– Stehlé-Lefèvre-Zimmermann, complexité heuristique

� �� � ���

.

– Limite pratique : � � � �

.

– Générateur

� � �

de Blum-Blum-Shub :

avec

� � � � � � bits consécutifs de

� � �

, on peut retrouver

.

– Nesterenko-Waldschmidt : il y a au plus

� � � � �

zéros consécutifs

dans la suite des bits de � � � � � , pour � � �� � � � � � .

02/12/2005 Damien STEHLÉ 31/43

Page 33: Algorithmique de la réduction de réseaux et application à

2) Arrondi des fonctions mathématiques.

Contributions.

Méthode générale pour trouver les � � �� � � � � � tels que :

� � � � � � � � � ��

mod

� � � � � � �

1. Pour � � � (pires cas) : complexité heuristique

� �� ��

.

2. Pour � � � �

: complexité heuristique polynomiale en �.

3. Variations pour construire les tables de Gal et casser un

générateur aléatoire dû à Littlewood.

02/12/2005 Damien STEHLÉ 32/43

Page 34: Algorithmique de la réduction de réseaux et application à

2) Arrondi des fonctions mathématiques.

Inversion d’une fonction quand les premiers bits sont perdus.

On veut retrouver � � �� � � � � � � tel que :

� � � � � � � � � � � � � �

| {z } �

� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �

� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �

� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �

� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �

� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �

� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �

� � � �� � � � � �� � � � � � � � � �

� � �

02/12/2005 Damien STEHLÉ 33/43

Page 35: Algorithmique de la réduction de réseaux et application à

2) Arrondi des fonctions mathématiques, l’algorithme de recherche des pires cas.

Méthode de Coppersmith (1/2).

On cherche les petites racines � � de :

� � � � � �� � � � � � � � � � � � � � � � �� � � �� � � � � � �

.

1. On construit des polynômes dont � � est racine modulo

��

:�� �� � � � �� � � � � �� � � � � � �� � � � � � � � ��

.

2. On construit un réseau associé à cette famille : les monômes

« indicent » les colonnes, les polynômes les lignes.

3. On LLL-réduit ce réseau.

4. On obtient

� � � � � tel que pour � petit,

� � � � � � � � ��

.

5. On calcule les racines de

� � sur

pour trouver � � .

02/12/2005 Damien STEHLÉ 34/43

Page 36: Algorithmique de la réduction de réseaux et application à

2) Arrondi des fonctions mathématiques, l’algorithme de recherche des pires cas.

Méthode de Coppersmith (2/2).

– Cas univarié : on peut trouver en temps polynomial déterministe

toutes les racines � � de

telles que

� � � � � � � �

.

– Cas multivarié :

- Il faut trouver plusieurs vecteurs courts dans le réseau.

- Les polynômes trouvés peuvent avoir des facteurs communs...

– L’analyse est heuristique dans le cas multivarié.

02/12/2005 Damien STEHLÉ 35/43

Page 37: Algorithmique de la réduction de réseaux et application à

2) Arrondi des fonctions mathématiques, l’algorithme de recherche des pires cas.

Déroulement général de l’algorithme d’inversion.

Entrée : � � �.

Sortie : Les � � � �� � � � � � avec

� � � � � � � � �� �

mod� � � � � �

.

Diviser

�� � � � � � en

� �� � intervalles de longueur

�� � . Pour chacun :

1. Approcher

par un polynôme�

, avec erreur

�� � � �

.

2. Chercher les racines de

� � � � � � � � � � � � � � � modulo 1,

avec

� � � � � � � �

et

� � � �� � � �

.

Famille de polynômes : �� � � � � � � � � � � �

3. Si échec, diviser l’intervalle en deux et recommencer.

02/12/2005 Damien STEHLÉ 36/43

Page 38: Algorithmique de la réduction de réseaux et application à

2) Arrondi des fonctions mathématiques, l’algorithme de recherche des pires cas.

Dans l’analyse : deux bornes importantes.

– Borne d’approximation polynomiale :

� � � � � � � � � � �� � � � �

– Borne de Coppersmith :

LLL doit renvoyer au moins deux vecteurs suffisamment courts.

– Pour estimer cela, on utilise «� ���

� � �dim

� � � � � � �

dim».

– Le réseau est donné par une matrice rectangulaire...

02/12/2005 Damien STEHLÉ 37/43

Page 39: Algorithmique de la réduction de réseaux et application à

2) Arrondi des fonctions mathématiques, remarques expérimentales.

Résultats expérimentaux.

– Implantation (GNU MP, MPFR) disponible sous GPL : wclr-1.1.

Pour � � �, complexité

� �� ��Pour � � � �

, complexité

� � � �� � Encore trop cher.

– Avec des fonctions algébriques : la méthode échoue très souvent.

– Pas d’échec observé pour � � � � � �� � � � �.

02/12/2005 Damien STEHLÉ 38/43

Page 40: Algorithmique de la réduction de réseaux et application à

2) Arrondi des fonctions mathématiques, remarques expérimentales.

Résultats expérimentaux.

Sur Opteron 2.4GhZ, pour � � � �

, avec wclr-1.1.

� � � dims des bases temps de calcul

� Lefèvre

� � ��� � � ��

ans

SLZ’04

� � � � � � � � � �

ans

ici

� � � � � � � � � ��

ans

ici

� � �� � � � � � ��

jours

02/12/2005 Damien STEHLÉ 39/43

Page 41: Algorithmique de la réduction de réseaux et application à

Algorithmique de la réduction de réseaux et application à la recherche de pires cas pour l’arrondi de fonctions mathématiques.

3) Conclusion et perspectives.

02/12/2005 Damien STEHLÉ 40/43

Page 42: Algorithmique de la réduction de réseaux et application à

3) Conclusion et perspectives.

Conclusion.

– Améliorations en algorithmique de la réduction des réseaux : petite

dimension, dimension quelconque, comportement pratique.

– Utilisation de la méthode de Coppersmith pour trouver les pires cas

pour l’arrondi de fonctions.

– Autres contributions : algorithme pgcd-BG-rapide, algorithme de

construction des tables de Gal, cryptanalyse d’un générateur

aléatoire dû à Littlewood.

02/12/2005 Damien STEHLÉ 41/43

Page 43: Algorithmique de la réduction de réseaux et application à

3) Conclusion et perspectives.

Problèmes ouverts (1).

– Améliorer l’algorithme LLL flottant à l’aide des idées de Schönhage,

Koy et Schnorr pour diminuer le nombre d’opérations arithmétiques.

– Décrire un algorithme LLL de complexité quasi-linéaire en

� � �

en

conservant une complexité polynomiale en

.

– Étudier les algorithmes permettant d’obtenir des vecteurs plus

courts que ceux donnés par LLL.

02/12/2005 Damien STEHLÉ 42/43

Page 44: Algorithmique de la réduction de réseaux et application à

3) Conclusion et perspectives.

Problèmes ouverts (2).

– Problème de l’heuristique dans la méthode de Coppersmith : quand

les polynômes obtenus sont-ils algébriquement dépendants ?

– Coût prohibitif de l’algorithme de recherche de mauvais cas :

améliorer les algorithmes de réduction de réseaux ? diminuer la

taille du réseau à réduire ?

– Peut-on faire mieux que � � � �

en temps polynomial ?

02/12/2005 Damien STEHLÉ 43/43