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 cœur 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 ?
École doctorale : Sciences et Ingénierie Direction : OLIVIER RUATTA Financement : Financement d'une fondation pour la recherche française