Projet de recherche doctoral numero :4704

Date depot: 1 janvier 1900
Titre: Cryptographie Post-Quantique Conception et Analyse
Directeur de thèse: Jean-Charles FAUGÈRE (LIP6)
Directeur de thèse: Ludovic PERRET (LIP6)
Domaine scientifique: Sciences et technologies de l'information et de la communication
Thématique CNRS : Non defini

Resumé: La cryptographie à clef publique est un pilier de la cybersécurité que nous utilisons quotidiennement pour garantir la confidentialité des communications électroniques (via https, IPSEC, VPN, SSH. . . ). La sécurité des protocoles que nous employons en pratique repose essentiellement sur la difficulté ma- thématique de deux problèmes : le logarithme discret (DLOG) et la factorisation des entiers (FACT). Il est bien connu qu’une percée technologique comme la construction d’un ordinateur quantique re- mettrait en cause la difficulté de ces deux problèmes [22] ; rendant ainsi complètement obsolète des primitives comme le chiffrement à clef publique RSA ou l’échange de clef Diffie-Hellman. Il est difficile d’imaginer la situation de panique que pourrait engendrer l’annonce de la conception d’un ordinateur quantique. Il est très probable que l’ensemble les canaux de communications électroniques soient paralysés. Nous ne sommes heureusement pas dans cette situation, mais il semble maintenant indispensable d’anticiper dès aujourd’hui un basculement technologique. L’objet de la cryptographique post-quantique est de concevoir des cryptosystèmes qui sont résistants aux attaques classiques comme quantiques. Cette branche de la cryptographie repose sur l’hypothèse fondamentale qu’il n’existe pas d’algorithme polynomial quantique pour résoudre les problèmes NP- durs [1]. C’est un sujet d’étude classique qui a débuté rapidement après l’algorithme de Shor [22]. Les cryptosystèmes post-quantiques les plus prometteurs [2] incluent : les cryptosystèmes multivariés, les cryptosystèmes à base de codes, les cryptosystèmes à base de réseaux qui sont basés sur la difficulté de trouver un vecteur court dans un réseau Euclidien et des cryptosystèmes à base de hachage qui utilisent la difficulté de trouver une collision, ou une pré-image, d’une fonction de hachage. De nombreux indicateurs démontrent que l’effort pour développer des cryptosystèmes post-quantiques s’intensifie actuellement. L’indicateur le plus significatif est certainement la nouvelle position de l’organisation de standardisation américain NIST. Cette organisme, qui a le pouvoir d’établir les normes américaines, a débuté en 2016 un processus [5] dont l’objectif est de normaliser des cryptosystèmes post-quantiques à clés publiques à l’horizon 2020. Avec un recul historique sur l’impact des normes du NIST, il semble probable que les standards dérivés de ce processus seront largement adoptés à travers le monde. L’effort de standardisation en cryptographie post-quantique n’est pas limité aux USA. On re- trouve un effort similaire en Europe avec l’ETSI 1, ainsi qu’au niveau mondial avec l’ISO (le groupe SC 27/WG 2 est dans une période d’étude sur la standardisation post-quantique). Au delà de ces organismes institutionnels, on constate également une prise de conscience au niveau des industriels. Nous pouvons citer, entre autres, le groupe de sensibilisation post-quantique de la Cloud Security Alliance 2 et le libre blanc publié par Hexatrust and Systematic sur “Cybersecurité & confiance numérique 3.” Il est donc très probable que la cryptographie post-quantique envahisse notre quotidien ces prochaines années ; le type de cryptographie post-quantique reste encore lui à définir. On peut donc anticiper une très forte activité, académique comme industrielle, dans le domaine ces prochaines années. Cette transition post-quantique est un risque et une opportunité pour les acteurs du secteur de la cyber- sécurité. Nous assistons en effet au renouvellement d’un pilier, certes de nature algorithmique, mais fondamental pour les industriels de la sécurité. Cette thèse s’inscrit dans le domaine très porteur de la cryptographie post-quantique. L’objectif de la thèse est double. Nous souhaitons d’une part analyser la sécurité des cryptosystèmes post-quantiques (Section 2.3) via la cryptanalyse algébrique et d’autre part proposer de nouveaux cryptosystèmes post-quantiques de type multivarié. Le cryptographie multivariée, qui date des années 80 [16], est une branche de la cryptographie post- quantique dont la sécurité repose sur la difficulté du problème PoSSo, c’est à dire le problème de trouver – si elle existe – une racine commune d’un ensemble de polynômes non-linéaires en plusieurs variables. Le problème PoSSo est NP-dur et sa difficulté n’est a priori pas remise en cause par l’émergence d’une ordinateur quantique [14]. La cryptographie multivariée a été largement éprouvée par la communauté cryptographique. On compte dans la littérature de nombreuses attaques, e.g. [17, 11, 7, 3]. La situation est maintenant stabilisée et quelques schémas émergent de l’épreuve du temps : typiquement UOV [15] et des variantes de HFE [18, 19]. Un défi de la cryptographie de la post-quantique consiste aujourd’hui à sélectionner des schémas qui pourraient effectivement être déployés en pratique.

Doctorant.e: Ryckeghem Jocelyn