Thèse Algorithmes Quantiques pour le Décodage de Codes Structurés Cryptanalyse Structurée et Réduction de Complexité H/F - Doctorat.Gouv.Fr

Établissement : Université de Limoges École doctorale : Sciences et Ingénierie Laboratoire de recherche : XLIM Direction de la thèse : OLIVIER RUATTA ORCID 0009000991555012 Début de la thèse : 2026-10-01 Date limite de candidature : 2026-09-01T23:59:59 Contexte. La cryptographie post-quantique vise des protocoles résistants aux attaques exploitant un ordinateur quantique, fondés notamment sur les réseaux arithmétiques et les codes correcteurs - problèmes réputés robustes face aux algorithmes quantiques connus. Les instances génériques produisant des clés trop volumineuses, on utilise des instances structurées (codes cycliques, quasi-cycliques), dont l'impact sur la sécurité reste mal connu : la structure algébrique pourrait devenir un vecteur d'attaque quantique efficace. Cette question, encore peu explorée, est le coeur de la thèse.Problématique. Les structures cycliques de certains codes peuvent-elles être exploitées par des algorithmes quantiques pour décoder avec une complexité inférieure aux attaques génériques ?Verrous : les réductions quantiques existantes (ex. [DART24]) s'appliquent à des instances non structurées, sans exploiter l'algèbre des anneaux de polynômes ; les codes cycliques (HQC, BIKE, variantes de Classic McEliece) sont compatibles avec la FFT et potentiellement la transformée de Fourier quantique (QFT) ; aucune étude n'a évalué si QFT combinée à Grover ou aux marches quantiques permet un gain exponentiel.Objectifs.Formaliser quantiquement le décodage des codes cycliques (oracles, réduction possible vers un calcul de période).Concevoir des algorithmes quantiques exploitant la structure algébrique.Analyser leur complexité (qubits, profondeur de circuit) face aux meilleures attaques classiques et quantiques génériques.Appliquer les résultats aux paramètres réels de HQC, BIKE, Classic McEliece, et évaluer leur sécurité quantique.Méthodologie. Modélisation algébrique (représentations polynomiales, liens FFT/QFT) et exploration des marches quantiques pour la recherche combinatoire structurée.Résultats attendus.Théoriques : nouvelles réductions quantiques exploitant la structure cyclique ; analyse comparée d'un éventuel gain exponentiel ; limites de l'approche quantique sur codes structurés.Pratiques : recommandations de paramètres ; évaluation de la sécurité quantique de candidats NIST (HQC, BIKE).Valorisation : publications (CRYPTO, Eurocrypt, PQCrypto, IEEE Trans. Inf. Theory) ; collaborations (ANSSI, Inria).Bibliographie.[DART24] Debris-Alazard, Remaud, Tillich, Quantum Reduction of Finding Short Code Vectors to the Decoding Problem, IEEE Trans. Inf. Theory 70(7), 2024.[DADW22] Debris-Alazard, Ducas, van Woerden, An Algorithmic Reduction Theory for Binary Codes, IEEE Trans. Inf. Theory 68(5), 2022.[KT17] Kachigar, Tillich, Quantum Information Set Decoding Algorithms, PQCrypto 2017.[CT23] Chailloux, Tillich, The Quantum Decoding Problem, arXiv:2310.20651.[Gro96] Grover, A fast quantum mechanical algorithm for database search, STOC 1996.[NIS] NIST, Post-Quantum Cryptography Standardization.Souhaitez-vous que je raccourcisse également la version anglaise dans les mêmes proportions ? Les conditions matériels sont classiques pour une thèse de mathématiques.Ce sujet prend place dans un projet plus large sur l'informatique quantique soutenue par l'initiative quantique néo-Aquitain NAQUIDIS.

Master de Mathématiques ou d'informatique théorique avec une spécialisation soit en informatique quantique, soit en algorithmique haute performance.