Description
Date depot: 5 avril 2022
Titre: Vers des outils de référence et de nouveaux algorithmes pour la résolution des systèmes polynomiaux en cryptographie
Directeur de thèse:
Charles BOUILLAGUET (LIP6)
Domaine scientifique: Sciences et technologies de l'information et de la communication
Thématique CNRS : Calcul arithmétique et formel, codage et cryptologie
Resumé: La résolution des systèmes polynomiaux sur un corps fini est un problème NP-complet classique. Aucun algorithme quantique ne peux les résoudre efficacement, et donc la sécurité de mécanisme cryptographiques à clef publique "post-quantique" peut reposer dessus. Dans le contexte de la cryptographie, les systèmes polynomiaux sont généralement quadratiques, le nombre de solution est non seulement fini mais mais faible (une seule en général) et le corps fini est de petite taille. Tout ceci donne une "saveur" spécifique au problème.
Ce projet de recherche doctoral se donne deux objectifs. Premièrement produire des implantations (open-source) qui vont définir l'état en matière de résolution de systèmes polynomiaux pour la cryptographie, modulo 2 d'une part, et sur de petits corps fini plus gros (modulo 31 par exemple) d'autre part. Ces implantations doivent à la fois être faciles à utiliser par des tiers (sur un laptop) et en même temps permettre de battre les records du monde (sur des clusters de serveurs de calcul). Il faudra les valider en... battant les records du monde.
Deuxièmement, il s'agit d'essayer d'améliorer les algorithmes eux-mêmes. Le but n'est pas d'obtenir un n-ème algorithme théorique sans intérêt dans le monde réel, mais de voir s'il est possible d'obtenir des algorithmes qui soient simultanément utilisables et d'une complexité exponentiellement plus faible que la force brute.
Résumé dans une autre langue: Solving systems of polynomial equations over a finite field is a classic NP-complete problem. No known quantum algorithm can solve it efficiently; for this reason, the security of some public-key cryptographic schemes has been based on its computational hardness. In the context of cryptography, polynomial systems are usually quadratic, have few solutions (most often only one) and they are defined over a small finite field. This gives a specific "flavor" to polynomial system solving in cryptography.
This PhD thesis proposal has two main objectives. First, produce open-source software that will define the state-of-the-art in terms of cryptographic polynomial system-solving. This requires separate algorithms in the special case of the binary field on the one hand, and other larger fields on the other hand. These programs shall be both easy to use (on a laptop, by relatively inexperienced used) and capable of setting world records (on large clusters of compute servers). They will be validated by... setting world records.
The second objective consists in improving the algorithms themselves. The goal is not to obtain the n-th theoreticaland impractical algorithm, but to explore the possibility of discovering an algorithm that is simultaneously practical and exponentially faster than brute-force.
Doctorant.e: Sauvage Julia