Description
Date depot: 22 mars 2022
Titre: Algorithmes pour le problème des plus proches voisins et application en cryptanalyse
Directeur de thèse:
Charles BOUILLAGUET (LIP6)
Encadrante :
Claire DELAPLACE (MIS)
Domaine scientifique: Sciences et technologies de l'information et de la communication
Thématique CNRS : Calcul arithmétique et formel, codage et cryptologie
Resumé: Le problème des plus proches voisins est le suivant : étant donné deux listes A et B contenant chacune N chaînes de n bits, il faut trouver toutes les paires (x, y) dans A x B telles que la distance de Hamming entre x et y est inférieure à un seuil donné. Tous les algorithmes modernes de décodage des codes linéaires aléatoires (qui servent à casser certains schémas cryptographiques "post-quantiques") se ramènent à la résolution du problème des plus proches voisins, mais de façon plus ou moins implicite.
De nombreux algorithmes ont été décrits pour résoudre le problème, mais jamais programmés ni testés en pratique. La thèse poursuit plusieurs objectifs : améliorer les algorithmes existants pour le problème des plus proches voisins ou en inventer de meilleurs ; décider leur utilité pratique pour la cryptanalyse du chiffrement McEliece ; explorer d'éventuelles modification des algorithmes de décodage des codes linéaires aléatoires pour exploiter au mieux le problème des plus proches voisins ; explorer leur applicabilité dans un contexte plus large (pour d'autres métriques que la distance de Hamming).
Résumé dans une autre langue: The (high-dimensional) nearest neighbor problem is the following: given two lists A and B, of size N, containing random n-bit strings, find all pairs (x, y) in A x B such that the Hamming distance between x and y is less than a given threshold. All efficient algorithms for decoding random linear codes (that can be used to break some "post-quantum" public-key cryptographic schemes) solve exponentially many instances of this problem, sometimes implicitly. Many algorithms for the nearest neighbor have been described, but they have not been implemented nor tested in practice.
This thesis proposal has several goals: improve existing algorithms for the nearest-neighbor problem or design new ones; decide their practical value in the context of the cryptanalysis of the McEliece encryption scheme; explore potential modifications of decoding algorithms to better exploit the nearest-neighbor problem; try to retrofit potential improvements to the boolean nearest-neighbor algorithms to other metrics (with potential applications to euclidean lattice problems)
Doctorant.e: Hamdad Mickael