Fondements de Learning With Errors (LWE)

L'apprentissage avec erreurs (LWE) de Regev (2005) : étant donné de nombreuses équations linéaires bruitées sur Z_q, trouver le vecteur secret s. Le bruit e est faible, mais empêche l'élimination de Gauss. Sans bruit, le système est facile à résoudre ; même avec un bruit infime, il devient difficile sur le plan computationnel.

Secret s ∈ Z_q^n. L'adversaire reçoit des échantillons (a_i, b_i), où a_i ∈ Z_q^n est aléatoire, b_i = + e_i mod q, et e_i est un faible bruit issu de la distribution χ (par exemple, une distribution gaussienne avec σ = √n). Objectif : trouver s à partir d'un nombre polynomial d'échantillons.

Sans bruit : b_i = mod q. L'élimination de Gauss permet de retrouver s en O(n^3). Avec du bruit : une seule équation erronée suffit à perturber l'élimination. Le bruit est suffisamment faible pour que le déchiffrement fonctionne avec la clé, mais suffisamment élevé pour empêcher la cryptanalyse.

Regev a démontré que LWE se réduit à des problèmes de réseaux dans le pire cas (SIVP, GapSVP), au moyen d'une réduction quantique. Cela signifie que si LWE est cassé, de nombreux problèmes difficiles sur les réseaux sont résolus — mais aucun algorithme quantique n'est connu pour les problèmes de réseaux. LWE est sûr contre les attaques post-quantiques.

RLWE remplace Z_q^n par l'anneau Z_q[x]/(f(x)), où f est un polynôme cyclotomique. Un échantillon RLWE encode n équations, ce qui est beaucoup plus efficace. RLWE constitue la base de Kyber (KEM), de Dilithium (signature) et des schémas de HE BFV/BGV/CKKS.

La sécurité dépend de : n (dimension, généralement 512-2048), q (module, 1024-2^60), σ (écart-type du bruit). Une valeur n plus grande et un rapport σ/q plus petit rendent le problème plus difficile. Les normes post-quantiques de NIST utilisent n=256 (dimension du module) avec k modules (k=2,3,4).

Clé publique : (A, b=As+e). Pour chiffrer le bit m : choisissez un r aléatoire, calculez le texte chiffré (u=A^T r, v = b^T r + m*q/2). Déchiffrement : v - s^T u = e^T r + m*q/2 ≈ m*q/2. Arrondissez à la valeur de m la plus proche. Le bruit e maintient m dissimulé dans le texte chiffré pendant le chiffrement.

LWE décisionnel : distinguer (a, As+e) de (a, u), où u est uniformément aléatoire. Ces deux distributions sont computationnellement indiscernables si LWE est difficile. C'est le fondement de la sécurité sémantique : pour les adversaires qui ne possèdent pas la clé secrète, les textes chiffrés ressemblent à du bruit aléatoire.

Les meilleures attaques connues utilisent BKZ (réduction de réseaux de Block Korkine-Zolotarev). Complexité : sous-exponentielle, mais non polynomiale. BKZ-β nécessite 2^{0.292β} opérations. Pour LWE-512 : sécurité d'environ 128 bits contre BKZ. Aucune accélération quantique de BKZ n'est connue.

Module-LWE (utilisé dans Kyber) est une version de RLWE sur des modules de rang k. Il offre une certaine flexibilité : k=2 pour une sécurité de 512 bits, k=3 pour 768 bits, k=4 pour 1024 bits. La sécurité et les performances évoluent avec k. NIST a sélectionné Kyber (renommé ML-KEM) comme norme PQC.

Sécurité de RSA/ECC : fondée sur la factorisation des entiers et le logarithme discret, vulnérables aux ordinateurs quantiques par l'intermédiaire de l'algorithme de Shor. Sécurité de LWE : fondée sur des problèmes de réseaux dans le pire cas, sans accélération quantique connue. Tailles des clés : clés LWE d'environ 1 Ko contre 256 octets pour RSA-2048. LWE est plus volumineux, mais résistant aux attaques quantiques.

Qu'est-ce qui rend LWE difficile à résoudre, même avec de nombreux échantillons ?

LWE : trouver le secret s à partir d'équations linéaires bruitées — difficile même pour les ordinateurs quantiques. RLWE utilise des anneaux de polynômes pour gagner en efficacité. Il constitue la base de Kyber, de Dilithium et des schémas de HE. Ensuite : les schémas de HE BGV et BFV pour les opérations sur les entiers.