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.
Prochains exposés
-
Polytopes in the Fiat-Shamir with Aborts Paradigm
Orateur : Hugo Beguinet - ENS Paris / Thales
The Fiat-Shamir with Aborts paradigm (FSwA) uses rejection sampling to remove a secret’s dependency on a given source distribution. Recent results revealed that unlike the uniform distribution in the hypercube, both the continuous Gaussian and the uniform distribution within the hypersphere minimise the rejection rate and the size of the proof of knowledge. However, in practice both these[…]-
Cryptographie
-
Primitive asymétrique
-
Mode et protocole
-
-
Post-quantum Group-based Cryptography
Orateur : Delaram Kahrobaei - The City University of New York