La sécurité de nombreux cryptosystèmes basés sur les codes correcteurs repose sur la difficulté du problème suivant : étant donnés une matrice H, un vecteur s et un entier w, trouver un vecteur e comportant au plus w coordonnées non nulles et vérifiant He = s. Ce dernier se nomme problème de décodage par syndrome. L’objectif principal de cette thèse est de proposer de nouveaux algorithmes pour le résoudre et d’affiner l’analyse de ceux existants.
De nombreux algorithmes de décodage utilisent de façon cruciale une sous-routine qui résout le problème des plus proches voisins. Dans un premier temps, nous étudions les méthodes de résolution de ce problème. En particulier, nous analysons l’algorithme de May–Ozerov pour le problème des plus proches voisins afin de le comparer à un algorithme plus classique appelé méthode des projections. Pour cela, nous établissons de nouvelles bornes sur la complexité de ces deux algorithmes qui prennent en compte les facteurs constants et polynomiaux. Ces résultats montrent que l’algorithme de May–Ozerov est galactique : bien que sa complexité possède un meilleur exposant asymptotique que la méthode des projections, il ne devient plus efficace que pour des instances de taille hors de portée en pratique. Nous montrons ainsi qu’utiliser la méthode des projections dans les algorithmes de décodage par ensemble d’information est le meilleur des deux choix.
Dans un second temps, nous étudions le problème de décodage par syndrome quasi-abélien, sur lequel repose la sécurité de plusieurs générateurs de corrélations pseudo-aléatoires. Nous réduisons ce problème à un problème d’interpolation de polynômes multivariés creux sur de petits corps finis. Nous développons ensuite de nouveaux algorithmes pour résoudre ce problème d’interpolation. D’une part des méthodes simples inspirées d’une idée de Richard Zippel, d’autre part une méthode plus avancée basée sur un plongement dans le corps des nombres complexes et sur l’acquisition comprimée. Ces algorithmes permettent d’obtenir des attaques pratiques contre plusieurs jeux de paramètres proposés pour le problème de décodage par syndrome quasi-abélien. En particulier, pour les paramètres agressifs du protocole F4OLEAGE, notre implémentation distingue la sortie du générateur de l’aléatoire avec un avantage supérieur à 60 % et récupère l’ensemble des polynômes secrets avec une probabilité supérieure à 13 %.