Algorithmes quantiques

Algorithmes quantiques pour le décodage de codes structurés : cryptanalyse structurée et réduction de complexité // Quantum algorithms for decoding of structured codes: cryptanalysis of structured systems and complexity reduction, 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)., Context. Post-quantum cryptography aims to design protocols resistant to attacks exploiting a quantum computer. Two main families of hard problems underpin these systems: lattice problems and error-correcting code problems. Unlike factoring or discrete logarithm, these problems appear robust against known quantum algorithms, as they belong to complexity classes (NP-complete in their generic versions) that seem resistant. However, generic instances yield very large keys and ciphertexts. To make these cryptosystems practical, structured instances are used (cyclic, quasi-cyclic codes). These structures reduce computational and storage costs, but their impact on security remains poorly understood: algebraic structure, unexploitable classically, could become an effective vector for quantum attacks. This still-emerging question is the core of the thesis. Problem statement and challenges. Central question: can the cyclic polynomial structures of certain codes be exploited by quantum algorithms to solve decoding with lower complexity than generic attacks? Challenges to address:

Existing quantum reductions (e.g. [DART24]) apply to unstructured decoding instances and do not exploit the underlying polynomial ring algebra. Cyclic codes, widely used in post-quantum candidates (HQC, BIKE, some Classic McEliece variants), are compatible with the fast Fourier transform and potentially with the quantum Fourier transform (QFT). No systematic study has yet assessed whether QFT combined with quantum search algorithms (Grover, quantum walks) yields an exponential gain relative to code dimension or number of errors.

Thesis objectives.

Quantum formalization of the decoding problem for cyclic codes: precisely define the oracles and quantum operations needed to model syndrome decoding (or short-vector search), aiming for a reduction to a period-finding problem. Design of quantum algorithms exploiting the algebraic structure, based on the proposed reductions. Complexity analysis (qubit count, circuit depth) of the proposed algorithms, compared with the best known classical attacks on these instances or quantum attacks on the generic problem. Application to real cryptosystems: transpose results to actual parameters of code-based post-quantum cryptosystems (HQC, BIKE, Classic McEliece with Goppa or quasi-cyclic codes), assessing their security against a quantum adversary.

Methodology. Research combining quantum complexity theory, algebra, and cryptanalysis: algebraic modeling via polynomial representations and evaluation-interpolation links to FFT/QFT; exploring quantum walks to improve combinatorial search in a structured space. Expected results.

Theoretical contributions: new quantum reductions exploiting cyclic structure for decoding; comparative complexity analysis showing a possible exponential gain; clarification of the limits of the quantum approach on structured codes. Practical contributions: concrete recommendations for parameter choices in code-based post-quantum cryptosystems; quantum security evaluation of NIST candidates (HQC, BIKE) against these new attacks. Dissemination: publications in leading conferences and journals (CRYPTO, Eurocrypt, PQCrypto, IEEE Trans. Inf. Theory); collaborations with academic and industrial teams (ANSSI, Inria).

Bibliography.

Master de Mathématiques ou d’informatique théorique avec une spécialisation soit en informatique quantique, soit en algorithmique haute performance. Master in mathematics or computer sciences specialized in quantum computing or high performance computing.

Début de la thèse : 01/10/2026

Nature du financement

Précisions sur le financement

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 ?, [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., Financement d’une fondation pour la recherche française

Présentation établissement et labo d’accueil

Université de Limoges

Etablissement délivrant le doctorat

Université de Limoges