Description
L'algorithme de Lenstra, Lenstra et Lovasz (LLL) pour réduire les bases de réseaux Euclidiens s'est avéré fort utile dans de nombreux domaines comme par exemple la cryptanalyse et la détection de relations linéaires entre des nombres réels. Etant donnée une base à coefficients entiers d'un réseau de dimension d avec des vecteurs de normes plus petites que B, LLL calcule une base LLL-réduite en temps O(d^6 log^3 B), en utilisant des opérations arithmétiques sur des entiers de taille O(d logB). Cette complexité est beaucoup trop élevée pour réduire des réseaux de taille ne serait-ce que modérée, pour lesquels l'algorithme LLL original n'est presque jamais utilisé. A la place, on se sert de variantes flottantes de LLL, où l'arithmétique entière utilisée dans le procédé d'orthogonalisation de Gram-Schmidt (central dans LLL) est remplacée par de l'arithmétique flottante. Malheureusement, ce procédé est connu comme étant instable numériquement dans le cas le pire: ni la correction ni la terminaison ne sont garanties.<br/> Dans cet exposé, nous introduirons l'algorithme LLL², qui est une variante nouvelle et naturelle de LLL flottant qui renvoie toujours des bases LLL-réduites en temps polynomial O(d^5 (d+logB) logB). Il s'agit de la première variante de LLL dont le temps d'éxécution croisse seulement de façon quadratique en logB sans utiliser de l'arithmétique rapide, comme c'est le cas pour les célèbres algorithmes d'Euclide et de Gauss. La complexité est au moins cubique pour toutes les autres variantes connues de LLL.
Prochains exposés
-
Séminaire C2 à INRIA Paris
Emmanuel Thomé et Pierrick Gaudry Rachelle Heim Boissier Épiphane Nouetowa Dung Bui Plus d'infos sur https://seminaire-c2.inria.fr/ -
Attacking the Supersingular Isogeny Problem: From the Delfs–Galbraith algorithm to oriented graphs
Orateur : Arthur Herlédan Le Merdy - COSIC, KU Leuven
The threat of quantum computers motivates the introduction of new hard problems for cryptography.One promising candidate is the Isogeny problem: given two elliptic curves, compute a “nice’’ map between them, called an isogeny.In this talk, we study classical attacks on this problem, specialised to supersingular elliptic curves, on which the security of current isogeny-based cryptography relies. In[…]-
Cryptography
-