Grundlagen von LWE und GitternGrundlagen von LWE und Gittern

Zusammenfassung

Kyber basiert seine Sicherheit auf dem Module-LWE-Problem (Learning With Errors über Moduln), einer Variante des klassischen LWE, definiert von Regev im Jahr 2005. LWE zu verstehen bedeutet zu verstehen, warum Kyber sicher ist und, noch wichtiger, wie lange es das sein könnte.

Das LWE-Problem

Gegeben ein Geheimnis s, eine Matrix A und einen Fehlervektor e:

s = geheimer Vektor (Dimension n)
A = zufällige Matrix (m × n)
e = kleiner Fehlervektor (aus einer Verteilung χ abgetastet)
b = A·s + e   (Modul q)

Suchproblem (Search-LWE): Gegeben (A, b), finde s.

Entscheidungsproblem (Decision-LWE): Gegeben (A, b), unterscheide, ob b = A·s + e oder ob b gleichmäßig zufällig ist.

Die Sicherheit hängt davon ab, dass, obwohl A·s deterministisch ist, der Fehler e das System schwer umkehrbar macht. Ohne e wäre es triviale lineare Algebra.

Warum es schwer ist

s aus (A, b) wiederherzustellen, ist äquivalent zum Lösen von Gitterproblemen, die im schlechtesten Fall NP-schwer sind. Regess Reduktion (2005) zeigte, dass das Brechen von LWE mindestens so schwer ist wie bestimmte Gitterprobleme im schlechtesten Fall (GapSVP, SIVP).

Module-LWE

Kyber verwendet Module-LWE, wobei A und s keine skalaren ganzen Zahlen, sondern Elemente eines Moduls über einem Polynomring sind:

R_q = Z_q[x] / (x^n + 1)

Wobei n = 256 für Kyber. Die Matrix A hat Einträge in R_q und die Dimension k × k (wobei k = 2, 3, 4 je nach Sicherheitsstufe).

A ∈ R_q^{k×k},  s ∈ R_q^{k},  e ∈ R_q^{k}
b = A·s + e

Vorteil gegenüber Standard-LWE: Module-LWE bietet ein Gleichgewicht zwischen Effizienz (Ringe ermöglichen schnelle Multiplikation via NTT) und Sicherheit (der Modul k steuert die Dimension ohne quadratisches Wachstum).

Warum Modul und nicht vollständiger Ring?

Ring-LWE (verwendet von NewHope zum Beispiel) operiert über einem einzelnen Ring (R_q). Module-LWE interpoliert zwischen Standard-LWE und Ring-LWE:

Die Fehlerverteilung

Kyber verwendet eine zentrierte Binomialverteilung CBD(η) anstelle einer diskreten Gauß-Verteilung. Dies vereinfacht die Implementierung (kein Tabellen-Sampling erforderlich) und vermeidet Timing-Angriffe.

Pr[ e = x ] = (C(2η, η+x)) / 2^(2η)

Für ML-KEM-512: η = 2. Für ML-KEM-768 und 1024: η = 3.

Der Modul q = 3329

Die Wahl von q = 3329 ist kein Zufall:

• Es ist eine Primzahl mit q ≡ 1 (mod 2n) für n = 256, was die Verwendung von NTT (Number Theoretic Transform) für schnelle Multiplikation in R_q ermöglicht.
• Es ist klein genug, damit Ciphertexts und Schlüssel kompakt sind.
• Es ist groß genug, damit der Fehler nicht überläuft und keine fehlerhaften Entschlüsselungen verursacht.

Die zentrale Vermutung

Die Sicherheit von Kyber (und der gesamten gitterbasierten Kryptographie) beruht auf der Vermutung, dass:

Es gibt keinen Quantenalgorithmus (und keinen klassischen), der Module-LWE für die Parameter von Kyber in Polynomialzeit löst.

Diese Vermutung ist plausibel, aber nicht bewiesen. Die Geschichte der Kryptographie lehrt, dass Härtevermutungen manchmal versagen. Was LWE von RSA/ECC unterscheidet, ist, dass kein Quantenanalogon von Shor für Gitter bekannt ist — aber das bedeutet nicht, dass keines entdeckt werden kann.

Referenzen

• Regev, O. (2005). "On lattices, learning with errors, random linear codes, and cryptography." STOC 2005.
• Bos, J. et al. (2018). "CRYSTALS-Kyber: A CCA-Secure Module-Lattice-Based KEM." EuroS&P 2018.
• Langlois, A. & Stehlé, D. (2015). "Worst-case to average-case reductions for module lattices." Designs, Codes and Cryptography.