Learning With Errors (LWE): Grundlagen

Learning With Errors (LWE) nach Regev (2005): Gegeben sind viele verrauschte lineare Gleichungen über Z_q; gesucht ist der geheime Vektor s. Das Rauschen e ist klein, verhindert aber die Gauß-Elimination. Ohne Rauschen ist das Gleichungssystem einfach zu lösen; bereits bei geringem Rauschen wird es rechnerisch schwierig.

Geheimnis s ∈ Z_q^n. Der Angreifer erhält Stichproben (a_i, b_i), wobei a_i ∈ Z_q^n zufällig ist und b_i = + e_i mod q gilt; e_i ist kleines Rauschen aus der Verteilung χ (z. B. gaußverteilt mit σ = √n). Aufgabe: s anhand polynomial vieler Stichproben zu finden.

Ohne Rauschen: b_i = mod q. Die Gauß-Elimination rekonstruiert s in O(n^3). Mit Rauschen: Bereits eine falsche Gleichung bringt die Elimination aus dem Tritt. Das Rauschen ist klein genug, damit die Entschlüsselung mit dem Schlüssel funktioniert, aber groß genug, um die Kryptoanalyse zu verhindern.

Regev bewies, dass sich LWE mithilfe einer Quantenreduktion auf Gitterprobleme im Worst Case (SIVP, GapSVP) reduzieren lässt. Das bedeutet: Wird LWE gebrochen, werden viele schwierige Gitterprobleme gelöst – bislang ist jedoch kein Quantenalgorithmus für Gitterprobleme bekannt. LWE ist postquanten-sicher.

RLWE ersetzt Z_q^n durch den Ring Z_q[x]/(f(x)) für ein zyklotomisches Polynom f. Eine RLWE-Stichprobe codiert n Gleichungen und ist dadurch wesentlich effizienter. RLWE bildet die Grundlage für Kyber (KEM), Dilithium (Signatur) und die HE-Schemata BFV/BGV/CKKS.

Die Sicherheit hängt von folgenden Parametern ab: n (Dimension, typischerweise 512–2048), q (Modulus, 1024–2^60), σ (Standardabweichung des Rauschens). Größeres n und ein kleineres Verhältnis σ/q machen das Problem schwieriger. Die Post-Quantum-Standards des NIST verwenden n=256 (Moduldimension) mit k Modulen (k=2,3,4).

Öffentlicher Schlüssel: (A, b=As+e). Bit m verschlüsseln: Wählen Sie ein zufälliges r und berechnen Sie das Chiffrat (u=A^T r, v = b^T r + m*q/2). Entschlüsseln: v - s^T u = e^T r + m*q/2 ≈ m*q/2. Runden Sie auf das nächstgelegene m. Das Rauschen e sorgt dafür, dass m während der Verschlüsselung im Chiffrat verborgen bleibt.

Decision-LWE: Unterscheide (a, As+e) von (a, u), wobei u gleichverteilt zufällig ist. Unter der Annahme der LWE-Sicherheit sind beide rechnerisch nicht unterscheidbar. Dies bildet die Grundlage der semantischen Sicherheit: Für Angreifer ohne den geheimen Schlüssel sehen Chiffrate wie zufälliges Rauschen aus.

Die besten bekannten Angriffe verwenden die Gitterreduktion BKZ (Block Korkine-Zolotarev). Ihre Komplexität ist subexponentiell, aber nicht polynomial. BKZ-β benötigt 2^{0.292β} Operationen. Für LWE-512 beträgt die Sicherheit gegen BKZ ungefähr 128 Bit. Für BKZ ist keine quantenbasierte Beschleunigung bekannt.

Module-LWE (wird in Kyber verwendet) ist RLWE über Modulen vom Rang k. Es bietet Flexibilität: k=2 für 512-Bit-Sicherheit, k=3 für 768 Bit und k=4 für 1024 Bit. Sicherheit und Leistung skalieren mit k. Das NIST hat Kyber (umbenannt in ML-KEM) als PQC-Standard ausgewählt.

Die Sicherheit von RSA/ECC basiert auf der Faktorisierung ganzer Zahlen bzw. dem diskreten Logarithmus (durch Shor quantengefährdet). Die LWE-Sicherheit basiert auf Gitterproblemen im Worst Case (keine bekannte quantenbasierte Beschleunigung). Schlüsselgrößen: LWE-Schlüssel etwa 1 KB gegenüber 256 Byte bei RSA-2048. LWE-Schlüssel sind größer, aber quantensicher.

Was macht LWE selbst bei vielen Stichproben schwierig zu lösen?

LWE: Den geheimen Schlüssel s aus verrauschten linearen Gleichungen finden – quantenresistent schwierig. RLWE verwendet zur Effizienzsteigerung Polynomringe. LWE und RLWE bilden die Grundlage für Kyber, Dilithium und HE-Schemata. Als Nächstes folgen die HE-Schemata BGV und BFV für Ganzzahloperationen.