Description
Date depot: 1 septembre 2020
Titre: Etude des cryptosystèmes post-quantiques fondés sur le problème MinRank
Directeur de thèse:
Jean-Pierre TILLICH (Inria-Paris (ED-130))
Domaine scientifique: Sciences et technologies de l'information et de la communication
Thématique CNRS : Non defini
Resumé: Cette thèse se propose en conséquence d'étudier la difficulté du problème de décodage pour la métrique rang à la fois dans le modèle de calcul classique et quantique.Jusqu'à présent deux approches ont été explorées pour résoudre ce problème: une approche combinatoire [0J02],[GRS16, $3],HT15],[AGHT18)- une approche algébrique consistant à modéliser le problème du décodage avec un système algébrique et à le résoudre avec des techniques de bases de Gröbner [FLP08, GRS16].Les cryptosystèmes basés sur une telle métrique passant le second tour [AAB+19, ABD+19] ont été dimensionnés par rapport à des attaques combinatoires qui avaient été jugées à lépoque beaucoup plus efficaces que les algorithmes derésolution de systèmes algébriques par calcul de bases de Gröbner. La situation a changé complètement depuis (BBB+20] où il a été montré qu'avec un choix adéquat de la modélisation algébrique, le système bilinéaire qui doit être résolu se comporte bien mieux qu'un système bilinéaire générique. La résolution monte en effet beaucoup moins haut en degré dans ce cas là. L'article BBB+20] en suivant une approche suivie dans [VBC+19] donne une explication algébrique de ce phénomène et donne un meilleur éclairage sur d'autres modélisations comme celle de Kipnis-Shamir pour résoudre ce problème. Depuis, la modélisation utilisée dans [BBB+20] a encore été améliorée [BBC*20] et a mis en évidence que la résolution de tels systèmes réclame une profonde compréhension de phénomènes algébriques dues à des égalités sur les mineurs des matrices mises en jeu.Compréhension algébrique de la modélisation algébrique [BBB+20].
Doctorant.e: Briaud Pierre