Description
Date depot: 1 janvier 1900
Titre: Stabilité numérique des algorithmes de réduction de réseaux
Directeur de thèse:
Antoine JOUX (CISPA Helmholtz Center for Information Sec)
Domaine scientifique: Sciences et technologies de l'information et de la communication
Thématique CNRS : Non defini
Resumé:
La réduction de réseaux est un outil très utile pour résoudre de nombreux problèmes algorithmiques sur les entiers. Il est très utilisé en cryptographie, à la fois comme technique de cryptanalyse et pour servir de base à des cryptosystèmes très variés. Ainsi, de nombreux systèmes totalement homomorphes proposés récemment s'appuient sur des problèmes difficiles liés à la réduction de réseaux.
L'étude des algorithmes de réduction de réseaux et de leurs possibles améliorations est donc un sujet important et d'actualité. Ce sujet est difficile et malgré les nombreux travaux déjà existants, il reste de nombreuses questions ouvertes dans ce domaine. Une des difficultés majeures est, lors de l'utilisation de nombres flottants pour l'approximation des bases othrogonalisées du réseau, de déterminer la précision minimale nécessaire.
A ce jour, deux approches sont connues. L'une heuristique, consiste à fixer une précision et à tenter par l'utilisation de techniques ad'hoc de limiter l'apparition d'erreurs majeures et de détecter les comportements anormaux risquant de conduire à des boucles infinies. L'autre plus théorique, permet de donner une borne linéaire en la dimension (pour le cas de l'algorithme L2) sur la précision nécessaire. Dans la pratique, chacune des deux approches a ses inconvénients. L'approche théorique implique d'utiliser une précision inutilement grande dans de nombreux cas alors que l'approche heuristique ne permet de garantir ni la complexité ni la correction du résultat. En pratique, des programmes tels que fplll de Stehlé mélange les deux approches en utilisant une méthode théorique pour certifier la sortie d'un algorithme heuristique. L'une des conséquences de la grande précision nécessaire en théorie est que la vérification du résultat devient la phase dominante du calcul. Pour s'affranchir de cela, l'objectif de la thèse sera de proposer des méthodes permettant de calculer en précision aussi petite que possible tout en auto-certifiant le résultat de la réduction sans faire appel à une précision supérieure.
Doctorant.e: Espitau Thomas