Thèse Etude des Solutions Optimales du Programme Linéaire de Delsarte et Application à la Réduction de Regev H/F - Doctorat.Gouv.Fr

Établissement : Institut Polytechnique de Paris École polytechnique École doctorale : Ecole Doctorale de l'Institut Polytechnique de Paris Laboratoire de recherche : LIX - Laboratoire d'informatique Direction de la thèse : Thomas DEBRIS-ALAZARD ORCID 0000000188640245 Début de la thèse : 2026-10-01 Date limite de candidature : 2026-08-31T23:59:59 La sécurité des schémas cryptographiques post-quantiques les plus connus et les plus répandus, c'est-à-dire des solutions implémentées sur nos appareils et résistantes à un ordinateur quantique, repose sur l'intractabilité des problèmes basés sur les réseaux euclidiens. Cela est démontré par le fait que l'Institut national américain des normes et des technologies (NIST) a déjà normalisé des schémas basés sur les réseaux euclidiens afin de garantir une sécurité à long terme. Ce succès remonte à l'introduction par Regev du problème « Learning with Errors » (LWE) (qui revient essentiellement à résoudre un système linéaire dans lequel certaines équations de la liste comportent des « erreurs »). L'intérêt principal de LWE pour les applications cryptographiques réside dans sa simplicité : il est presque évident de concevoir des schémas de chiffrement dont la sécurité repose sur la difficulté du LWE. Mais s'agit-il vraiment d'un problème difficile ? Pouvons-nous attribuer sa difficulté à une source identifiable, nous assurant ainsi de son caractère intractable ? Pour répondre à cette question, il faut remonter dans le temps, avant l'introduction du LWE.
Historiquement, de nombreuses tentatives ont été menées pour calculer efficacement des points dans un réseau de norme euclidienne courte. Elles étaient certainement motivées par le fait que cela permettrait de disposer d'un algorithme efficace pour casser RSA. Cependant, cette approche n'a pas abouti. Au lieu de cela, RSA a finalement été cassé par l'algorithme quantique de Shor, qui ne repose pas sur un sous-programme calculant des points de réseau à norme courte.Probablement motivé par la recherche d'un algorithme efficace pour calculer des points de réseau à norme courte, Regev s'est tourné vers la puissante approche de Shor. Étonnamment, Regev a montré que si l'on utilise l'algorithme de Shor, mais avec une autre transformée de Fourier quantique pour calculer des points de réseau à norme courte, il faut d'abord résoudre le problème LWE. Regev a donc fourni, via l'algorithme de Shor, une réduction : le problème LWE est plus difficile que la recherche d'un point de réseau court, ce qu'on appelle le problème SIS. Plutôt que de proposer des attaques, l'adaptation de l'algorithme de Shor par Regev a permis d'identifier le problème LWE comme un problème adapté à la cryptographie. Cette identification a constitué une avancée majeure : la difficulté du problème LWE est actuellement l'une des hypothèses les plus utilisées pour garantir la sécurité des schémas cryptographiques résistants à l'informatique quantique.Il s'avère que la réduction de Regev a récemment fait l'objet d'un regain d'intérêt significatif, mais pas dans le but d'assurer la sécurité. Certains travaux ont montré qu'elle pouvait être utilisée pour obtenir des avantages quantiques, c'est-à-dire pour résoudre, à l'aide d'algorithmes quantiques efficaces, certains problèmes considérés comme intractables en informatique classique ! Malheureusement, ces travaux ont révélé de profondes limites : ils se limitaient à des problèmes sans grand intérêt cryptographique. Dans la recherche de nouveaux résultats, on peut donc naturellement se demander : ces limites ne sont-elles pas inhérentes à l'approche de Regev elle-même ?L'objectif de cette thèse est précisément de montrer que le cadre de Regev est en effet intrinsèquement limité : il peut être étendu à une théorie plus large et plus puissante permettant de dériver des attaques quantiques contre des primitives basées sur des réseaux euclidiens. La cryptographie connait depuis désormais une décennie une profonde transformation. En effet, nous perdrons la sécurité des crypto-systèmes actuellement déployés une fois qu'un ordinateur efficace aura été construit (ce qui au vu des récents progrès ne saurait tarder). La communauté cryptographique s'attèle donc à développer et faciliter le développement de solutions cryptographiques sûres même face à une ordinateur quantique. Cette thèse se déroule dans ce contexte et a pour but d'analyser la sécurité des crypto-systèmes proposés les plus prometteurs.

Les compétences attendues sont à l'intersection de - la théorie de l'information (notion de capacité, connaissances de base des codes correcteurs) - l'algorithmique quantique - programmation linéaire

• Programmation
• Crypto