Apprentissage avec erreurs : le problème difficile

Le problème de l’apprentissage avec erreurs (LWE) a été introduit par Oded Regev en 2005 comme fondement de la cryptographie post-quantique. Étant donné une matrice aléatoire A sur Z_q et un vecteur b = As + e, l’objectif est de trouver le vecteur secret s. Le vecteur e est une petite erreur tirée d’une distribution gaussienne discrète, ce qui rend le problème calculatoirement insoluble.

Dans le problème LWE, A est une matrice aléatoire de taille m x n, échantillonnée uniformément sur Z_q, où q est un module premier. Le secret s est un vecteur à n dimensions et e est un petit vecteur d’erreur dont les composantes sont tirées d’une loi gaussienne étroite. Même en connaissant la structure de A, un adversaire ne peut pas distinguer b d’un vecteur uniformément aléatoire.

Il existe deux formulations standard de LWE. Le LWE de recherche consiste à retrouver le secret s à partir de nombreux échantillons (A, b). Le LWE décisionnel consiste à distinguer les échantillons (A, As + e) de paires uniformément aléatoires (A, u). Les deux formulations sont équivalentes en temps polynomial : un algorithme qui résout l’une peut être transformé pour résoudre l’autre.

Le terme d’erreur dans LWE est tiré d’une distribution gaussienne discrète sur les entiers, paramétrée par l’écart type sigma. De petites valeurs de sigma garantissent que e est court par rapport à q, ce qui fait que b ressemble presque à As modulo q. Si sigma était nul, il n’y aurait aucune erreur et le système pourrait être résolu par élimination de Gauss ; l’erreur est donc essentielle à la difficulté du problème.

Regev a démontré une réduction remarquable : résoudre des échantillons LWE du cas moyen est au moins aussi difficile que résoudre des instances du problème du vecteur le plus court (SVP) dans des réseaux. Cela signifie que si vous pouvez casser LWE efficacement, vous pouvez résoudre efficacement n’importe quel problème de réseau. Aucun algorithme classique ou quantique connu ne permet de résoudre SVP dans le pire cas en temps polynomial.

Contrairement à RSA et ECC, aucun algorithme quantique connu ne procure d’accélération exponentielle contre LWE. L’algorithme de Grover offre au mieux une accélération quadratique, et les meilleurs algorithmes quantiques pour les réseaux, des variantes de BKZ, ne cassent pas LWE lorsque les paramètres sont correctement choisis. LWE constitue ainsi une base solide pour la sécurité post-quantique.

La sécurité de LWE est régie par trois paramètres : la dimension n, qui correspond à la longueur du secret, le module q et l’écart type de l’erreur sigma. Une valeur plus grande de n et un rapport q/sigma plus petit accroissent la sécurité. Pour atteindre une sécurité post-quantique de 128 bits, les valeurs courantes sont n = 1024, q autour de 12289 et sigma autour de 3.2. L’outil d’estimation des réseaux d’Albrecht et de ses collègues sert à évaluer la sécurité concrète.

Le problème de la solution entière courte (SIS) est une hypothèse de difficulté liée aux réseaux, utilisée pour les signatures. Étant donnée une matrice aléatoire A sur Z_q, il faut trouver un vecteur court non nul x tel que Ax = 0 mod q. SIS constitue la base des fonctions de hachage et des schémas de signature dans le domaine des réseaux, en complément de LWE, qui sous-tend le chiffrement et l’encapsulation de clés.

Un schéma de chiffrement LWE simple fonctionne comme suit : la clé publique est (A, b = As + e) et la clé secrète est s. Pour chiffrer un bit m, l’expéditeur calcule (u, v) = (A^T r, b^T r + m * floor(q/2)) pour un vecteur binaire aléatoire r. Le déchiffrement calcule v - s^T u et arrondit le résultat pour retrouver m. Ce schéma atteint la sécurité IND-CPA sous l’hypothèse LWE.

LWE a permis un large éventail de constructions cryptographiques allant au-delà du chiffrement de base. Elles comprennent le chiffrement entièrement homomorphe (FHE), le chiffrement fondé sur l’identité (IBE), le chiffrement fondé sur les attributs (ABE) et les protocoles d’échange de clés. CRYSTALS-Kyber, désormais ML-KEM et normalisé sous la référence FIPS 203, est le schéma fondé sur LWE le plus déployé en pratique.

La cryptographie fondée sur LWE est déjà intégrée aux systèmes de production. Google et Cloudflare ont mené des expériences TLS utilisant Kyber entre 2018 et 2020. Chrome et Firefox ont ajouté la prise en charge de ML-KEM-768 lors de négociations TLS hybrides en 2024. Le protocole Signal a ajouté une couche post-quantique (PQXDH) utilisant ML-KEM-1024 pour la confidentialité persistante, afin de protéger la confidentialité à long terme des messages contre de futurs ordinateurs quantiques.

Quelle affirmation décrit le mieux la garantie de difficulté du problème LWE ?

LWE est l’une des hypothèses de difficulté post-quantiques les plus étudiées, soutenue par une solide réduction du pire cas à partir de problèmes de réseaux. Ses trois paramètres (n, q, sigma) régissent le compromis entre sécurité et performances. LWE résiste aux attaques quantiques et sous-tend des schémas normalisés par NIST. Comprendre LWE ouvre la voie à toute la cryptographie moderne fondée sur les réseaux, notamment ML-KEM et ML-DSA.