Thèse Algèbre Linéaire pour les Bases de Gröbner H/F - Doctorat.Gouv.Fr

Établissement : Université Paris-Saclay GS Informatique et sciences du numérique École doctorale : Sciences et Technologies de l'Information et de la Communication Laboratoire de recherche : Laboratoire de Mathématiques de Versailles Direction de la thèse : Sorina IONICA Début de la thèse : 2026-10-01 Date limite de candidature : 2026-07-20T23:59:59 En cryptanalyse, certaines attaques se modélisent sous la forme de systèmes polynomiaux à plusieurs variables, définis sur des corps finis. Pour résoudre ces systèmes, les méthodes les plus performantes reposent sur le calcul de bases de Gröbner, à l'aide d'algorithmes fondés sur l'algèbre linéaire appliquée à certaines matrices, appelées matrices de Macaulay. Pour les paramètres utilisés en cryptographie, ces matrices sont de très grande taille, et leur manipulation devient coûteuse tant en temps de calcul qu'en mémoire.Dans certains cas, on obtient des systèmes polynomiaux structurés, comme les systèmes bi-homogènes. La mission confiée au doctorant consistera à développer et mettre en oeuvre un algorithme dédié à la résolution de systèmes polynomiaux bilinéaires, qui constituent une classe particulière de systèmes bi-homogènes de degré 2. En effet, il est bien connu que, pour résoudre de tels systèmes, le calcul d'une base de Gröbner revient à manipuler des matrices de Macaulay plus petites, correspondant à des blocs de bi-degré. Cependant, aucune implémentation logicielle efficace d'un tel algorithme n'est actuellement disponible, et la comparaison de ses performances avec celles des algorithmes classiques, tels que F4 et F5, demeure une question ouverte.Dans un second temps, la thèse se concentrera sur la résolution de systèmes bilinéaires issus de la modélisation de l'attaque par calcul d'indices appliquée aux courbes elliptiques. La cryptanalyse algébrique est une méthode bien établie pour étudier la sécurité des systèmes en cryptographie. Elle consiste à modéliser l'attaque sous formes d'équations polynomiales à plusieurs variables. Le coût de l'attaque dépend alors de la complexité de l'algorithme de résolution des systèmes polynomiaux, le plus souvent un algorithme de calcul de bases de Groebner. L'objectif de la thèse est d'évaluer la sécurité des systèmes cryptographiques dont la sécurité se réduit à la reduction des systèmes polynomiaux multivariés structurés. Le doctorant travaillera sur l'analyse de complexité des algorithmes de calcul de bases de Grobner des systèmes bilinéaires. Cette analyse implique à la fois la manipulation des outils venant de l'algèbre commutative, de l'algèbre linéaire et de la théorie de la complexité. Il devra valider ses résultats par des expériences permettant de soutenir d' éventuelles conjectures sur le comportement des algorithmes.

Les compétences en cryptographie, calcul formel et complexité sont souhaitées. Une expérience de développement sera également la bienvenue.

• Business Intelligence
• Cryptographie