Cryptanalyse quantique de schémas classiques et post-quantiques, et de la sécurité de certains algorithmes post-quantiques basés sur les réseaux euclidiens

Titre : 

Cryptanalyse quantique de schémas classiques et post-quantiques, et de la sécurité de certains algorithmes post-quantiques basés sur les réseaux euclidiens

Title : 

Quantum cryptanalysis of classical and post-quantum schemes, and the security of some lattice-based cryptographic problems

Résumé : 

Dans la première partie de cette thèse, j’étudie deux algorithmes quantiques : l’algorithme de Shor et l’algorithme quantique de Prange. L’algorithme de Shor permet de casser, en temps polynomial, les cryptosystèmes RSA et ECDSA, deux cryptosystèmes encore largement utilisés aujourd’hui. L’algorithme quantique de Prange résout en temps exponentiel le « Syndrome Decoding Problem ». La sécurité de cryptosystèmes post-quantiques basés sur des codes, tels que McEliece, HQC et BIKE, repose sur ce problème. Je présente des optimisations mémoire de l’algorithme de Shor et de l’algorithme quantique de Prange, pour l’ensemble de ces applications.
Dans la deuxième partie de cette thèse, je m’intéresse au problème « Learning With Error» (LWE) et au problème d’isomorphisme de réseaux structuré (modLIP). Le problème LWE est à la base de la sécurité de la plupart des systèmes cryptographiques modernes fondés sur les réseaux. Parmi ceux-ci, Kyber et Dilithium ont récemment été standardisés par le NIST. Le problème modLIP, en revanche, est un problème beaucoup plus récent, proposé par Ducas et van Woerden en 2022. Il sous-tend notamment la sécurité de la signature Hawk. Je présente une réduction du problème modLIP à un problème de quaternions, puis je présente une amélioration d'une attaque quantique duale sur le problème LWE.