Simultaneous Approximation for Lattice-Based Cryptography

1. Problemstellung und Motivation

Hintergrund:
Gitterbasierte Kryptographie (Lattice-based Cryptography) gilt als einer der vielversprechendsten Ansätze für Post-Quanten-Kryptographie, da sie Sicherheitsbeweise vom Worst-Case zum Average-Case bietet und homomorphe Verschlüsselung ermöglicht. Ein Hauptnachteil herkömmlicher gitterbasierter Systeme sind jedoch die großen öffentlichen Schlüsseln.

Das Dilemma:
Um die Schlüssellänge zu reduzieren, wurden „Ideal-Lattices" eingeführt, die durch algebraische Strukturen (Polynomringe) kompakter beschrieben werden können. Es gibt jedoch Bedenken, dass Ideal-Lattices nicht so sicher sind wie allgemeine Gitter, da spezifische Angriffe (z. B. von Campbell et al.) existieren, die Approximationsfaktoren bieten, die besser sind als bei allgemeinen Gittern.

Das Ziel:
Die Arbeit untersucht eine neue Klasse von Gittern, die Simultaneous Approximation (SA) Gitter, um zu prüfen, ob diese eine Alternative bieten, die sowohl kleine Schlüsselgrößen ermöglicht als auch die Härte der zugrundeliegenden Probleme (SVP, SIVP, CVP) im Worst-Case beibehält.

2. Methodik und Definitionen

Die Autorin definiert SA-Gitter als Gitter der Dimension $n$, die durch die Spalten der Einheitsmatrix $I_n$ und einen Vektor $x \in \mathbb{Q}^n$ erzeugt werden. Dies erfordert nur $n+1$ ganze Zahlen zur Beschreibung, im Gegensatz zu $n^2$ für allgemeine Gitter.

Neue Problemdefinitionen:
Basierend auf der Struktur von SA-Gittern werden drei neue Probleme definiert, die den klassischen Gitterproblemen entsprechen:

1. SAP (Simultaneous Approximation Problem): Entspricht dem approximativen Shortest Vector Problem (SVP). Gesucht ist ein ganzzahliger Faktor $b_0$, sodass $\{b_0 x\}$ (der Vektor der gebrochenen Teile) kurz ist.
2. SIAP (Shortest Independent Approximation Problem): Entspricht dem Shortest Independent Vectors Problem (SIVP). Gesucht sind $n$ linear unabhängige Faktoren $b_i$, sodass die Vektoren $\{b_i x\}$ kurz sind.
3. CAP (Closest Approximation Problem): Entspricht dem Closest Vector Problem (CVP). Gesucht ist ein Faktor $b_0$, der einen Zielvektor $t$ im SA-Gitter approximiert.

Der Reduktionsansatz (Algorithmus 1):
Der Kern der Arbeit ist ein deterministischer Algorithmus, der ein beliebiges Gitter $L = M\mathbb{Z}^n$ durch ein SA-Gitter approximiert.

• Idee: Das Gitter wird so transformiert, dass es fast orthogonal skaliert ist. Dies geschieht durch die Konstruktion einer Matrix $\tilde{M} = c \cdot \text{adj}(M) + A$, wobei $A$ eine kleine Störmatrix ist.
• Koprimitäts-Constraint: Um sicherzustellen, dass die Spalten von $\tilde{M}$ zusammen mit einem Vektor $b$ das Gitter $\mathbb{Z}^n$ erzeugen, müssen bestimmte Determinanten von Untermatrizen koprim sein.
• Perturbation: Der Algorithmus iteriert und passt die Einträge von $A$ schrittweise an, bis die geforderten Determinanten koprim sind. Dies nutzt Eigenschaften der Jacobsthal-Funktion und des Euklidischen Algorithmus.

3. Schlüsselbeiträge und Ergebnisse

1. Dimensions- und Gap-erhaltende Reduktionen:
Die Arbeit beweist, dass die allgemeinen Probleme SVP$_\gamma$, SIVP$_\gamma$ und CVP$_\gamma$ in polynomialer Zeit und mit polynomialem Speicherbedarf auf die entsprechenden Probleme in SA-Gittern (SAP, SIAP, CAP) reduziert werden können.

• Diese Reduktionen sind deterministisch.
• Sie erhalten die Approximationsgüte ($\gamma$) und die Dimension des Gitters.
• Die Eingabelänge skaliert nur mit $O(n^2 \log(n))$.

2. Verbesserte Schranke für Integer-Inflation:
Ein kritischer Faktor für die Sicherheit und Schlüssellänge ist die „Integer Inflation" (das Wachstum der Bitlänge der Zahlen während der Berechnung).

• Martin (2020) hatte eine Schranke von $O(n^4 \log(nk))$ für die Bitlänge.
• VanLandingham verbessert dies auf $O(n^2 \log(nk))$.
• Dies wird erreicht, indem statt Polynomringen (wie bei Martin) direkt mit ganzen Zahlen gearbeitet wird und die Perturbationen effizienter gesteuert werden.

3. Optimalität der Reduktion:
In Abschnitt 3.4 wird bewiesen, dass diese Reduktion in Bezug auf die Integer-Inflation optimal ist.

• Ein Theorem zeigt, dass jede Reduktion, die eine sub-quadratische Inflation ($O(n^{2-\epsilon})$) erreichen würde, implizieren würde, dass man kurze Vektoren in allgemeinen Gittern mit einem sub-exponentiellen Approximationsfaktor finden könnte. Da dies als unmöglich für polynomielle Algorithmen gilt, ist die $O(n^2)$-Schranke optimal.

4. Härte der Probleme (NP-Härte):
Aufgrund der Reduktionen werden die neuen SA-Probleme als NP-hart klassifiziert:

• SIAP$_\gamma$ und CAP$_\gamma$ sind für jede Konstante $\gamma$ unter den Normen $\ell_1, \ell_2, \ell_\infty$ NP-hart.
• SAP$_\gamma$ ist unter $\ell_\infty$ für jedes $\gamma$ NP-hart und unter $\ell_1, \ell_2$ für bestimmte $\gamma$-Schwellenwerte NP-hart (unter randomisierten Reduktionen).

4. Signifikanz für die Kryptographie

Die Arbeit hat folgende wichtige Implikationen:

1. Sicherheit ohne Kompromisse: Im Gegensatz zu Ideal-Lattices, bei denen die Härte der Probleme im Worst-Case nicht garantiert ist, zeigen die Reduktionen, dass SA-Gitter genau so schwer zu knacken sind wie allgemeine Gitter.
2. Potenzial für kleinere Schlüssel: Da SA-Gitter durch $n+1$ statt $n^2$ Parametern beschrieben werden können, bieten sie theoretisch die Möglichkeit, öffentliche Schlüssel deutlich zu verkleinern, ohne die Sicherheitseigenschaften zu verlieren.
3. Optimale Effizienz: Die Verbesserung der Integer-Inflation von $O(n^4)$ auf $O(n^2)$ ist entscheidend für die praktische Anwendbarkeit, da sie die Größe der benötigten Zahlen und damit den Speicherbedarf für sichere Parameter reduziert.
4. Neue Forschungsrichtung: Die Arbeit etabliert SA-Gitter als eine vielversprechende neue Klasse für die Konstruktion von kryptographischen Systemen, die sowohl effizient als auch sicher sind.

Zusammenfassend liefert das Paper einen rigorosen mathematischen Beweis, dass die Approximation von Gittern durch SA-Gitter eine sichere und effiziente Methode ist, um die Schlüsselgrößen in der gitterbasierten Kryptographie zu reduzieren, wobei die Worst-Case-Härte der zugrundeliegenden Probleme vollständig erhalten bleibt.