Conception et analyse d'attaques duales en cryptographie à base de codes et de réseaux

Dans cette thèse, nous concevons et analysons des attaques duales pour résoudre le problème du décodage. En cryptographie basée sur les codes, les attaques duales ont été introduites par Al-Jabri en 2001 avec l'algorithme de décodage statistique. Cependant, il s'est avéré que son algorithme n'était pas compétitif face aux décodeurs par ensembles d'informations (ISD). En commençant par l'algorithme de Prange en 1962, les ISDs ont été la famille dominante de décodeurs ces 60 dernières années et sont utilisés pour paramétrer les schémas basés sur les codes. Notre contribution principale est d'améliorer drastiquement les attaques duales et de montrer qu'elles peuvent battre les meilleurs ISDs pour certains régimes de paramètres. En particulier, notre meilleure attaque bat asymptotiquement de manière significative tous les décodeurs connus auparavant pour des codes de taux constant inférieur à 0,42 à la distance de Gilbert-Varshamov. Ce résultat a été obtenu en revisitant l'algorithme de décodage statistique d'Al-Jabri et en le généralisant à l'aide d'une stratégie de découpage pour réduire le problème du décodage à un problème qui est essentiellement un problème d'apprentissage de parité avec du bruit (LPN). Nous le résolvons ensuite en utilisant des solveurs standards. Une partie de notre travail réside aussi dans le développement d'outils pour analyser ces attaques: nous n'utilisons pas les hypothèses d'indépendance qui étaient traditionnellement utilisées pour analyser le décodage statistique et qui doivent être utilisées avec beaucoup de précautions. Nos outils sont basés sur la formule de sommation de Poisson et un modèle pour la distribution de l'énumérateur de poids des codes linéaires aléatoires. Nous basons l'analyse de nos attaques sur ce modèle et le vérifions expérimentalement. Nous concevons aussi une variante de notre attaque la plus avancée qui a, à des facteurs polynomiaux près, la même performance que celle-ci mais que nous pouvons prouver entièrement sans utiliser ce modèle. La deuxième partie de ce travail est dédiée à la conception et à l'analyse d'attaques duales en cryptographie basée sur les réseaux. Ici, le problème que nous ciblons est le problème d'apprentissage avec du bruit (LWE). Dans ce contexte, les attaques duales ont été récemment grandement améliorées, en partie en utilisant une stratégie de découpage similaire. En particulier, deux attaques récentes, d'abord par Guo & Johansson en 2021 puis par Matzov en 2022, ont affirmé réduire la sécurité du standard NIST Kyber (ML-KEM). Cependant, Ducas & Pulles ont montré en 2023 que les hypothèses d'indépendance clés utilisées dans l'analyse de ces récentes attaques à base de réseaux étaient erronées. Cela a laissé ouverte la question de savoir comment les analyser et si elles pouvaient réellement fonctionner comme prévu. Nous concevons une légère variante de ces attaques et fournissons de nouveaux outils pour les analyser sans ces hypothèses. En particulier, nous montrons que notre attaque s'approche dangereusement des revendications de sécurité de Kyber et que nous surpassons légèrement ces récentes attaques. Cela règle la controverse sur la question de savoir si une attaque duale (par crible) pouvait réellement fonctionner comme prévu.