Description
Nous présenterons l'algorithme d'Ajtai, Kumar et Sivakumar pour résoudre le problème du plus court vecteur d'un réseau Euclidien. Ce problème a été prouvé NP-dur sous des réductions randomisées par Ajtai en 1996. Cet algorithme, présenté à STOC 2001, a une complexité probabiliste $2^O(n)$ en temps et en espace. Il bat donc la précédente borne de complexité ($n^{O(n)}$), qui correspond à l'algorithme de Kannan (1983).<br/> En utilisant l'algorithme BKZ de Schnorr, cela permet d'améliorer la taille des vecteurs que l'on peut obtenir en temps polynomial. Il existe une controverse quant à la practicabilité de ce dernier résultat, du fait de la constante du $O(.)$ de $2^{O(n)}$. Schnorr estime la complexité à $O(poly(n).2^{30n})$. Nous argumenterons pourquoi il s'agirait plutôt de $O(poly(n).2^n)$. En-dehors de ces améliorations de bornes de complexité, l'algorithme d'Ajtai, Kumar et Sivakumar apporte surtout un nouvel éclairage sur l'algorithmique des réseaux Euclidiens, en donnant une vision beaucoup plus géométrique que LLL et ses variantes.
Next sessions
-
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
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
-