Damien VIDAL soutient sa thèse de doctorat en informatique le lundi 14 septembre à 10h dans l'Amphithéâtre Figlarz, Bâtiment des Minimes
Résumé
Avec l'essor de la cryptographie post-quantique, de nouvelles familles de schémas cryptographiques ont vu le jour.
Parmi elles figurent les schémas de cryptographie multivariée dont la sécurité repose sur la difficulté de résoudre un système quadratique défini sur un corps fini (problème MQ).
Plusieurs algorithmes ont été proposés pour résoudre ce problème.
Lors de nos travaux, nous nous sommes concentrés sur des systèmes polynomiaux surdéterminés.
Pour de tels systèmes définis dans les corps finis de petite taille, l'algorithme Crossbred est le plus efficace en pratique.
Cette thèse propose une étude rigoureuse de cet algorithme et de sa complexité.
Pour ce faire, nous introduisons une variante de Crossbred adaptée aux polynômes homogènes.
Cette variante permet d'établir des séries génératrices dans le cas général (polynômes à coefficients dans F_q) et dans le cas booléen (les coefficients des polynômes et les solutions sont dans F_2).
Ces séries nous permettent de connaître, dans chacun des cas, les paramètres pour lesquels l'algorithme s'exécute correctement.
Ces calculs sont réalisés sous des hypothèses de semi-régularité, corroborées par des résultats expérimentaux.
Après avoir établi ce cadre théorique, nous nous intéressons à l'amélioration de Crossbred.
Pour cela, nous proposons d'abord un critère permettant d'éviter certains calculs inutiles.
Nous déterminons ensuite la taille minimale des matrices qui sont manipulées lors de l'algorithme.
Cela réduit significativement le nombre de calculs à effectuer et améliore ainsi l'efficacité de l'algorithme.
Jury
Magali Bardet, MCF, Université de Rouen, Rapporteure
Pierre-Jean Spaenlehauer, CR, INRIA Nancy - Grand Est, Rapporteur
Charles Bouillaguet, MCF, Sorbonne Université, Examinateur
Elisa Gorla, PU, Université de Neuchatel, Examinatrice
Jacques Patarin, PU, UVSQ, Université Paris Saclay, Examinateur
Antoine Joux, Chercheur, CISPA Helmholtz, Examinateur
Claire Delaplace, MCF, Université de Picardie Jules Verne, Co-directrice de thèse
Sorina Ionica, PU, UVSQ, Université Paris Saclay, Directrice de thèse
