Learning With Errors: das schwierige Problem

Das Learning-With-Errors-(LWE-)Problem wurde 2005 von Oded Regev als Grundlage für Post-Quanten-Kryptografie eingeführt. Gegeben seien eine zufällige Matrix A über Z_q und ein Vektor b = As + e. Ziel ist es, den geheimen Vektor s zu finden. Der Vektor e ist ein kleiner Fehler, der aus einer diskreten Gaußverteilung stammt, wodurch das Problem rechnerisch nicht praktikabel lösbar wird.

Beim LWE-Problem ist A eine zufällig aus Z_q gleichverteilt gezogene m x n-Matrix, wobei q ein Primmodul ist. Das Geheimnis s ist ein n-dimensionaler Vektor, und e ist ein kleiner Fehlervektor, dessen Einträge aus einer schmalen Gaußverteilung stammen. Selbst wenn ein Angreifer die Struktur von A kennt, kann er b nicht von einem gleichverteilten Zufallsvektor unterscheiden.

Es gibt zwei standardmäßige Formulierungen von LWE. Beim Such-LWE soll das Geheimnis s anhand vieler Stichproben (A, b) wiederhergestellt werden. Beim Entscheidungs-LWE soll zwischen Stichproben (A, As + e) und gleichverteilten Zufallspaaren (A, u) unterschieden werden. Die beiden Formulierungen sind polynomiell äquivalent. Das bedeutet, dass sich ein Algorithmus, der die eine Formulierung löst, so umwandeln lässt, dass er auch die andere löst.

Der Fehlerterm in LWE stammt aus einer diskreten Gaußverteilung über den ganzen Zahlen, die durch die Standardabweichung sigma parametrisiert wird. Kleine sigma-Werte stellen sicher, dass e im Vergleich zu q kurz ist, sodass b fast wie As mod q aussieht. Wäre sigma gleich null, gäbe es keinen Fehler und das System könnte durch Gauß-Elimination gelöst werden. Der Fehler ist daher entscheidend für die Schwierigkeit des Problems.

Regev bewies eine bemerkenswerte Reduktion: Das Lösen von LWE-Stichproben aus dem Average-Case ist mindestens so schwierig wie das Lösen von Worst-Case-Instanzen des Problems des kürzesten Vektors (SVP) auf Gittern. Das bedeutet: Wenn Sie LWE effizient brechen können, können Sie jedes Gitterproblem effizient lösen. Es ist kein klassischer oder quantenbasierter Algorithmus bekannt, der SVP im Worst-Case in polynomieller Zeit löst.

Im Gegensatz zu RSA und elliptischer-Kurven-Kryptografie ist kein Quantenalgorithmus bekannt, der gegen LWE eine exponentielle Beschleunigung ermöglicht. Grovers Algorithmus bietet höchstens eine quadratische Beschleunigung, und die besten quantenbasierten Gitteralgorithmen, Varianten von BKZ, brechen LWE bei korrekt gewählten Parametern nicht. Dadurch bildet LWE eine starke Grundlage für Post-Quanten-Sicherheit.

Die Sicherheit von LWE wird durch drei Parameter bestimmt: die Dimension n (Länge des Geheimnisses), das Modul q und die Fehler-Standardabweichung sigma. Ein größeres n und ein kleineres Verhältnis q/sigma erhöhen die Sicherheit. Für eine Post-Quanten-Sicherheit von 128 Bit werden typischerweise n = 1024, q ungefähr 12289 und sigma ungefähr 3,2 verwendet. Zur Bewertung der konkreten Sicherheit wird das Tool Lattice Estimator von Albrecht et al. eingesetzt.

Das Short Integer Solution (SIS)-Problem ist eine verwandte Annahme zur Gitterhärte, die für Signaturen verwendet wird. Gegeben eine zufällige Matrix A über Z_q soll ein kurzer, von null verschiedener Vektor x gefunden werden, für den Ax = 0 mod q gilt. SIS bildet die Grundlage für Hashfunktionen und Signaturschemata in der Gitterkryptografie und ergänzt LWE, das Verschlüsselung und Schlüsselkapselung zugrunde liegt.

Ein einfaches LWE-Verschlüsselungsschema funktioniert folgendermaßen: Der öffentliche Schlüssel ist (A, b = As + e), und der geheime Schlüssel ist s. Um ein Bit m zu verschlüsseln, berechnet der Sender für einen zufälligen binären Vektor r (u, v) = (A^T r, b^T r + m * floor(q/2)). Bei der Entschlüsselung wird v - s^T u berechnet und gerundet, um m wiederherzustellen. Dieses Schema erreicht IND-CPA-Sicherheit unter der LWE-Annahme.

LWE hat neben der einfachen Verschlüsselung eine große Bandbreite kryptografischer Konstruktionen ermöglicht. Dazu gehören vollständig homomorphe Verschlüsselung (FHE), identitätsbasierte Verschlüsselung (IBE), attributbasierte Verschlüsselung (ABE) und Schlüsselaustauschprotokolle. CRYSTALS-Kyber, jetzt ML-KEM und als FIPS 203 standardisiert, ist das in der Praxis am weitesten eingesetzte LWE-basierte Verfahren.

LWE-basierte Kryptografie hält bereits Einzug in Produktionssysteme. Google und Cloudflare führten von 2018 bis 2020 TLS-Experimente mit Kyber durch. Chrome und Firefox unterstützten 2024 ML-KEM-768 in hybriden TLS-Handshakes. Das Signal Protocol ergänzte mit PQXDH eine Post-Quanten-Schicht, die ML-KEM-1024 für Forward Secrecy verwendet und die langfristige Vertraulichkeit von Nachrichten gegen künftige Quantencomputer schützt.

Welche Aussage beschreibt die Härtegarantie des LWE-Problems am besten?

LWE ist eine der am gründlichsten untersuchten Annahmen zur Post-Quanten-Härte und wird durch eine starke Worst-Case-Reduktion von Gitterproblemen gestützt. Seine drei Parameter (n, q, sigma) bestimmen den Kompromiss zwischen Sicherheit und Leistung. LWE widersteht Quantenangriffen und bildet die Grundlage für von NIST standardisierte Verfahren. Das Verständnis von LWE ist der Einstieg in die moderne gitterbasierte Kryptografie, einschließlich ML-KEM und ML-DSA.