Sommaire

  • Cet exposé a été présenté le 12 mars 2004.

Description

  • Orateur

    Damien Stehlé - INRIA Lorraine - ENS

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

  • CryptoVerif: a computationally-sound security protocol verifier

    • 05 septembre 2025 (13:45 - 14:45)

    • IRMAR - Université de Rennes - Campus Beaulieu Bat. 22, RDC, Rennes - Amphi Lebesgue

    Orateur : Bruno Blanchet - Inria

    CryptoVerif is a security protocol verifier sound in the computational model of cryptography. It produces proofs by sequences of games, like those done manually by cryptographers. It has an automatic proof strategy and can also be guided by the user. It provides a generic method for specifying security assumptions on many cryptographic primitives, and can prove secrecy, authentication, and[…]
    • Cryptography

Voir les exposés passés