Grunderna i Learning With Errors (LWE)

Learning With Errors (LWE) av Regev (2005): givet många brusiga linjära ekvationer över Z_q ska den hemliga vektorn s hittas. Bruset e är litet men förhindrar Gausselimination. Utan brus är systemet enkelt; även med mycket litet brus blir det beräkningsmässigt svårt.

Hemlig s ∈ Z_q^n. Angriparen tar emot prover (a_i, b_i), där a_i ∈ Z_q^n är slumpmässig, b_i = + e_i mod q och e_i är litet brus från fördelningen χ (till exempel Gaussisk med σ = √n). Uppgiften är att hitta s givet polynomiellt många prover.

Utan brus: b_i = mod q. Gausselimination återställer s i O(n^3). Med brus förstör även en enda felaktig ekvation elimineringen. Bruset är tillräckligt litet för att dekryptering ska fungera med nyckeln, men tillräckligt stort för att förhindra kryptoanalys.

Regev visade att LWE kan reduceras till gitterproblem i värsta fall (SIVP, GapSVP) med en kvantreduktion. Det innebär att om LWE bryts löses många svåra gitterproblem — men ingen kvantalgoritm är känd för gitterproblem. LWE är postkvantsäkert.

RLWE ersätter Z_q^n med ringen Z_q[x]/(f(x)) för ett cyklotomiskt polynom f. Ett RLWE-prov kodar n ekvationer — mycket effektivare. RLWE ligger till grund för Kyber (KEM), Dilithium (signatur) och HE-schemana BFV/BGV/CKKS.

Säkerheten beror på: n (dimension, vanligtvis 512-2048), q (modul, 1024-2^60) och σ (brusets standardavvikelse). Större n och ett mindre förhållande σ/q innebär högre svårighetsgrad. NIST:s postkvantstandarder använder n=256 (moduldimension) med k moduler (k=2,3,4).

Offentlig nyckel: (A, b=As+e). Kryptera biten m: välj ett slumpmässigt r och beräkna chiffertexten (u=A^T r, v = b^T r + m*q/2). Dekryptera: v - s^T u = e^T r + m*q/2 ≈ m*q/2. Avrunda till närmaste värde för m. Bruset e gör att chiffertexten döljer m under krypteringen.

Decision-LWE: skilj (a, As+e) från (a, u), där u är uniformt slumpmässig. Dessa är beräkningsmässigt omöjliga att skilja åt under antagandet att LWE är svårt. Detta utgör grunden för semantisk säkerhet — chiffertexter ser ut som slumpmässigt brus för angripare utan den hemliga nyckeln.

De bästa kända attackerna använder BKZ (Block Korkine-Zolotarev), en gitterreduktion. Komplexiteten är subexponentiell men inte polynomiell. BKZ-β kräver 2^{0.292β} operationer. För LWE-512 är säkerheten ≈ 128 bitar mot BKZ. Ingen kvantacceleration är känd för BKZ.

Module-LWE (som används i Kyber) är RLWE över moduler av rang k. Det ger flexibilitet: k=2 för 512-bitars säkerhet, k=3 för 768-bitars och k=4 för 1024-bitars. Säkerhet och prestanda skalar med k. NIST valde Kyber (omdöpt till ML-KEM) som PQC-standard.

Säkerheten hos RSA/ECC bygger på heltalsfaktorisering och diskreta logaritmer, som är sårbara för kvantdatorer via Shors algoritm. LWE-säkerheten bygger på gitterproblem i värsta fall, utan någon känd kvantacceleration. Nyckelstorlekar: LWE-nycklar är cirka 1 KB jämfört med 256 byte för RSA-2048. LWE är större men kvantsäkert.

LWE: hitta den hemliga s från brusiga linjära ekvationer — svårt även för kvantdatorer. RLWE använder polynomringar för effektivitet. Det ligger till grund för Kyber, Dilithium och HE-scheman. Nästa steg: HE-schemana BGV och BFV för heltalsoperationer.