Description
Date depot: 10 novembre 2021
Titre: Cryptographie post-quantique : Conception, analyse et mise en oeuvre d'algorithmes de décodage générique
Directeur de thèse:
Nicolas SENDRIER (Inria-Paris (ED-130))
Domaine scientifique: Sciences et technologies de l'information et de la communication
Thématique CNRS : Calcul arithmétique et formel, codage et cryptologie
Resumé: L'objet de cette thèse est d'avancer dans la compréhension des algorithmes permettant de le résoudre le problème du décodage générique, en particulier sur leur mise en œuvre. Il s'agit d'un travail fondamental pour dimensionner les paramètres des cryptosystèmes fondés sur les codes.
La sécurité des primitives fondées sur les codes repose sur la difficulté du problème du décodage par syndrome. C'est le cas pour les systèmes soumis au NIST, mais d'une façon générale pour tous les schémas fondés sur les codes, authentification à apport de connaissance nul, signature numérique, ... Résoudre ce problème constitue la plupart du temps la meilleure attaque connue contre ces schémas et le coût de résolution, estimé ou mesuré, servira à dimensionner les paramètres de ces schémas en fonction du niveau de sécurité requis.
Il s'agira dans un premier temps de déterminer quelles sont les variantes d'ISD (Information Set Decoding), la principale technique de décodage générique, les plus adaptées à une mise en oeuvre effective. Les variantes les plus avancées ont de meilleures performances asymptotiques, mais ont souvent un facteur polynomial mal connu dans leur coût ainsi que des contraintes en terme de mémoire qui peuvent affecter leur effectivité. À ce jour, si le comportement asymptotique des algorithmes est connu et permet d'établir leur hierarchie, très peu de travaux ont été menés pour comprendre leur hérarchie effective pour des tailles utilisées en cryptographie. Les techniques les plus avancées requièrent souvent plus de mémoire, ce qui les rend moins performants en pratique. Mais le coût en mémoire peut parfois être réduit par des modifications algorithmiques, en réduisant la quantité de mémoire nécessaire ou bien en changeant la structure d'accès: une liste de grande taille peut-être stoquée dans une table de hachage et nécessiter un accès alétoire couteux, ou bien être triée à sa création avec un temps d'accès réduit par la suite. Des algorithmes les plus performants asymptotiquement peuvent être modifiés en ce sens, en vue de leur utilisation effective, certaines de ces modifications étant succeptible de fournir un gain effectif pour des tailles « utiles ».
Il y a eu des évolutions récentes en cryptographie fondées sur les codes, en particulier l'usage de corps finis non binaires et l'usage d'erreurs de grand poids. La généralisation au cas q-aire a déjà à fait l'objet d'études, mais la situation n'est pas encore stabilisée pour les variantes les plus performantes d'ISD. La recherche de mots de gros poids à fait l'objet de travaux qui méritent d'être examinés et éventuellement prolongés, en particulier en vue de leur mise en oeuvre.
Un autre point mérite une attention particulière: les variantes d'ISD utilisant les techniques de « nearest neighbors ». Ces méthodes sont mal comprises pour leur mise en oeuvre. Ce sont les plus performantes asymptotiquement, mais elles souffrent d'un surcoût important, sous la forme d'un facteur polynomial, généralement indéterminé et difficile à évaluer, et qui pourrait les rendre inutiles pour des tailles cryptographiques. De récentes évolutions de ces méthodes sont susceptibles de corriger ces défauts. Leur compréhension et leur mise en oeuvre présente donc un grand intérêt.
Doctorant.e: Meyer-Hilfiger Charles