Alle Erklärungen und Visualisierungen aus der Tutoring-Session. Zum Wiederholen vor dem Vortrag.
Ein Gitter ist die Menge aller ganzzahligen Kombinationen von Basisvektoren. Stell dir schiefes Karopapier vor — die Ecken der Parallelogramme sind die Gitterpunkte, und die Seitenvektoren bilden die Basis.
Formal: L = { z₁b₁ + z₂b₂ + ... + zₙbₙ | zᵢ ∈ ℤ }
Der entscheidende Unterschied zur linearen Algebra: Bei Vektorräumen darfst du reelle Zahlen verwenden und erreichst jeden Punkt. Bei Gittern nur ganze Zahlen → du bekommst diskrete Punkte.
Basen sind nicht eindeutig: Dasselbe Gitter kann durch komplett unterschiedliche Basisvektoren beschrieben werden. Manche Basen sind „gut" (kurze, fast senkrechte Vektoren → SVP leicht lösbar), manche „schlecht" (lange, fast parallele Vektoren → SVP schwer). Man kann nicht einfach orthonormalisieren, weil das reelle Koeffizienten bräuchte — erlaubt sind nur ganzzahlige unimodulare Transformationen (det = ±1).
Grundidee der Gitter-Krypto: Öffentlicher Schlüssel = schlechte Basis, privater Schlüssel = gute Basis desselben Gitters.
Gegeben eine Basis B, finde den kürzesten Nicht-Null-Vektor. Die Länge dieses Vektors heißt λ₁(L). Minkowski hat 1889 bewiesen, dass so ein Vektor immer existiert — aber ihn finden ist das Problem.
Statt den exakt kürzesten Vektor zu finden, reicht einer, der höchstens γ-mal so lang ist. Drei Varianten:
Suchversion (SVP_γ): Finde einen Vektor v mit ‖v‖ ≤ γ · λ₁.
Schätzversion (EstSVP_γ): Gib die Länge λ₁ bis auf Faktor γ genau an.
Entscheidungsversion (GapSVP_γ): Gegeben Basis B und Wert d, unterscheide: Ist λ₁ ≤ d (YES) oder λ₁ > γ·d (NO)? Alles dazwischen ist Grauzone (Promise-Problem) — dort darf die Antwort beliebig sein. In der Visualisierung: blauer Kreis = YES-Grenze (d), oranger Kreis = NO-Grenze (γ·d), gelbe Zone dazwischen = der „verbotene" Bereich, den das Problem ignoriert.
γ = 1 → NP-hart (Ajtai 1998)γ = Konstante → NP-hart (Micciancio 2001)γ ≈ √n → NP ∩ coNP (Aharonov & Regev 2005)γ = 2^O(n) → in P (LLL löst das)Gegeben ein Gitter und einen externen Punkt t (nicht im Gitter), finde den nächstgelegenen Gitterpunkt. In der Visualisierung: roter Punkt mit Kreuz = Zielpunkt t, grün umringter Punkt = nächster Gitterpunkt, gestrichelte Linie = minimale Distanz.
Verhältnis zu SVP: SVP ≤p CVP (Polynomialzeit-Reduktion: Man kann SVP auf CVP reduzieren, indem man Basis verdoppelt und t geschickt wählt). Die Umkehrung ist unbekannt — CVP gilt als das natürlich schwerere Problem. Typische Anwendung in der Kryptografie: t ist ein verrauschter Geheimtext, der nächste Gitterpunkt ist die eigentliche Nachricht.
P = effizient lösbar. NP = Lösung schnell überprüfbar. NP-hart = mindestens so schwer wie alles in NP. coNP = Ablehnung schnell verifizierbar. NP ∩ coNP = beides verifizierbar → vermutlich nicht NP-hart.
Ajtai hat SAT auf SVP reduziert: Aus jeder SAT-Formel baut er ein Gitter, bei dem der kürzeste Vektor verrät, ob die Formel erfüllbar ist. Aber: Die Reduktion braucht Zufall (randomisiert). Ob es deterministisch geht, ist seit 26 Jahren offen.
Micciancio (2001) verschärft: Selbst Approximation bis auf jeden konstanten Faktor γ bleibt NP-hart.
Ab γ ≈ √n liegt GapSVP in NP ∩ coNP. Die NP-Seite ist trivial (kurzen Vektor vorzeigen). Die coNP-Seite ist der Durchbruch:
Fun Fact: Aharonov & Regev haben das zuerst quantenmechanisch bewiesen (QMA) und dann "dequantisiert" — den Quantenbeweis in einen klassischen umgewandelt.
RSA sagt: "Faktorisieren zufälliger Zahlen ist hoffentlich schwer." Aber es gibt keinen Beweis dafür. Vielleicht sind 99% der zufälligen Instanzen leicht — dann wäre RSA unsicher. Bogdanov & Trevisan haben gezeigt, dass so eine Worst-Case-to-Average-Case-Verbindung für allgemeine NP-Probleme vermutlich unmöglich ist.
Für Gitter ist es anders: Wenn du zufällige SIS-Instanzen lösen kannst, kannst du jede beliebige Worst-Case-SVP-Instanz lösen. Die Reduktion baut aus der schwierigsten SVP-Instanz zufällige SIS-Instanzen. Löst jemand die, kannst du die Lösung zurückübersetzen.
SIS (Short Integer Solution): Gegeben eine zufällige Matrix A, finde einen kurzen Vektor z mit Az = 0 mod q.
Nimmt eine "schlechte" Basis und macht sie "besser". Zwei Bedingungen:
Größenreduktion: Gram-Schmidt-Koeffizienten |μ| ≤ ½ — jeder Vektor zeigt so wenig wie möglich in Richtung der vorherigen.
Lovász-Bedingung: Die Gram-Schmidt-Vektoren dürfen nicht zu schnell kürzer werden.
Funktioniert wie Bubble Sort — vergleiche Nachbarn, tausche wenn nötig. Polynomielle Laufzeit, aber exponentieller Approximationsfaktor 2^{(n-1)/2}.
Enumeration (Kannan 1983): Erst Basis reduzieren, dann systematisch alle Vektoren durchprobieren. Wie Baumsuche mit Pruning. Laufzeit n^{O(n)} (superexponentiell), aber nur poly(n) Speicher. Praxistauglich bis Dimension ~60-80.
Sieving (AKS 2001): Starte mit vielen zufälligen Gittervektoren, finde nahe Paare, ersetze durch ihre Differenz. Wie ein Sieb, das immer kürzere Vektoren erzeugt. Laufzeit 2^{n+o(n)} (besser), aber auch 2^{n+o(n)} Speicher (schlechter).
| Algorithmus | Faktor γ | Laufzeit | Speicher |
|---|---|---|---|
| LLL (1982) | 2^{(n-1)/2} | poly(n) | poly(n) |
| BKZ-k | 2^{O(n/k)} | 2^{O(k)} | poly(n) |
| Enumeration (1983) | 1 (exakt) | n^{O(n)} | poly(n) |
| Sieving (2001) | 1 (exakt) | 2^{n+o(n)} | 2^{n+o(n)} |
| Voronoi (2010) | 1 (exakt) | Õ(4^n) | Õ(2^n) |
RSA und ECC werden durch Shors Algorithmus gebrochen. Die NIST-Standards seit August 2024 basieren auf Gitterproblemen:
ML-KEM (Kyber): Schlüsselaustausch, basiert auf Module-LWE.
ML-DSA (Dilithium): Digitale Signaturen, basiert auf Module-LWE + Module-SIS.
SLH-DSA (SPHINCS+): Hashbasiertes Backup, falls Gitter gebrochen werden.
Zuletzt aktualisiert: April 2026. Alle Visualisierungen sind interaktiv — klick dich durch die Tabs.