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.
Next sessions
-
Attacking the Supersingular Isogeny Problem: From the Delfs–Galbraith algorithm to oriented graphs
Speaker : 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
-
-
Verification of Rust Cryptographic Implementations with Aeneas
Speaker : Aymeric Fromherz - Inria
From secure communications to online banking, cryptography is the cornerstone of most modern secure applications. Unfortunately, cryptographic design and implementation is notoriously error-prone, with a long history of design flaws, implementation bugs, and high-profile attacks. To address this issue, several projects proposed the use of formal verification techniques to statically ensure the[…] -
Endomorphisms via Splittings
Speaker : Min-Yi Shen - No Affiliation
One of the fundamental hardness assumptions underlying isogeny-based cryptography is the problem of finding a non-trivial endomorphism of a given supersingular elliptic curve. In this talk, we show that the problem is related to the problem of finding a splitting of a principally polarised superspecial abelian surface. In particular, we provide formal security reductions and a proof-of-concept[…]-
Cryptography
-