Attacks on Sparse LWE and Sparse LPN with new Sample-Time tradeoffs

1. Problemstellung

Das Paper befasst sich mit der kryptographischen Härte von zwei fundamentalen Problemen: Learning With Errors (LWE) und Learning Parity with Noise (LPN), wobei diese in ihrer sparse (dünnbesetzten) Variante betrachtet werden.

• Sparse LWE/LPN: Im Gegensatz zum Standard-LWE/LWE, bei dem die Vektoren $a \in \mathbb{Z}_q^n$ zufällig gewählt werden, haben bei der sparse Variante die Vektoren nur $k$ von Null verschiedene Einträge ($k \ll n$). Dies wird oft für effizientere kryptographische Primitive (z. B. schnellere Schlüsselerzeugung, kleinere Ciphertexts) genutzt.
• Herausforderung: Während die Härte von sparse LPN über $\mathbb{Z}_2$ gut untersucht ist, war die Analyse von sparse LWE/LPN über höheren Moduli $q$ (wo $q$ mindestens polynomial in der Sicherheitsparameter ist) bisher unzureichend erforscht.
• Ziel: Die Autoren wollen die Komplexität dieser Probleme genauer analysieren und neue Tradeoffs zwischen der Anzahl der benötigten Stichproben (Sample Complexity, $m$) und der Laufzeit (Time Complexity) für Angriffe auf diese Probleme finden.

2. Methodik: Verallgemeinerung der Kikuchi-Methode

Die Kernmethode des Papers ist die Verallgemeinerung der Kikuchi-Methode, die ursprünglich von Wein et al. (JACM 2019) und Gupta et al. (SODA 2026) für den Fall $q=2$ (k-XOR) entwickelt wurde. Die Autoren erweitern diese auf beliebige Moduli $q$.

Der Ansatz besteht aus folgenden Schritten:

1. Transformation zu Produktgleichungen:
   Lineare Gleichungen über $\mathbb{Z}_q$ werden in Produktgleichungen über die $q$-ten Einheitswurzeln $\Omega_q = \{1, \omega_q, \dots, \omega_q^{q-1}\}$ umgewandelt. Eine Gleichung $\sum a_i x_i = b$ wird zu $\prod x_i^{a_i} = b$.

2. Konstruktion des Kikuchi-Graphen:
   Aus einer Instanz von $k$-LIN$_q$ (sparse lineare Gleichungen) wird ein gerichteter Graph konstruiert.

   • Knoten: Entsprechen Teilmengen von Index-Koeffizienten-Paaren der Größe $l$ (wobei $k/2 \le l \le n$ ein Tradeoff-Parameter ist). Der Raum der Knoten hat die Größe $N = \binom{n}{l} q^l$.
   • Kanten: Werden basierend auf den Gleichungen der Instanz definiert. Eine Gleichung verknüpft zwei Knoten $T_1, T_2$, wenn ihre Differenz die Gleichung ergibt. Um die Analyse zu erleichtern, wird der Graph so konstruiert, dass er symmetrisch ist (für jede Kante $T_1 \to T_2$ gibt es auch $T_2 \to T_1$ mit konjugiertem Label), was die Matrix hermitesch macht.

3. Zwei Angriffsstrategien:
   Die Autoren nutzen den Graphen auf zwei verschiedene Weisen, um zwischen einer „gepflanzten" (planted, d.h. mit Geheimnis und Rauschen) und einer zufälligen Instanz zu unterscheiden.

   • A. Spektrale Methode (Spectral Method):

     • Berechnet die spektrale Norm (den größten Eigenwert) der Adjazenzmatrix des Kikuchi-Graphen.
     • Bei einer zufälligen Instanz ist der Erwartungswert der Norm nahe 0.
     • Bei einer gepflanzten Instanz ist der Erwartungswert signifikant größer (proportional zum Rauschen und dem Durchschnittsgrad).
     • Vorteil: Funktioniert für beliebige Rauschverteilungen und beliebige Moduli $q$ (keine Primzahlbedingung).
     • Nachteil: Benötigt, dass die linken Seiten der Gleichungen gleichverteilt sind.

   • B. Methode der q-ary Covers (Closed Walk Method):

     • Sucht nach geschlossenen Wegen (closed walks) im Graphen, die sogenannten q-ary Covers entsprechen. Ein q-ary Cover ist eine Multimenge von Gleichungen, bei der die Summe der Koeffizienten für jede Variable $0 \pmod q$ ist.
     • Für LPN wird das Produkt der rechten Seiten dieser Covers analysiert. Im gepflanzten Fall weicht dieses Produkt signifikant von 0 ab (Anti-Konzentration), während es im zufälligen Fall nahe 0 liegt.
     • Für LWE mit beschränktem Rauschen wird geprüft, ob das Skalarprodukt des Covers mit dem rechten Vektor klein ist.
     • Vorteil: Bietet eine fast quadratische Beschleunigung gegenüber der spektralen Methode bei gleicher Stichprobengröße. Funktioniert auch bei nicht-uniform verteilten linken Seiten.
     • Nachteil: Erfordert, dass $q$ eine Primzahl ist, und für LWE eine untere Schranke für $q$ bezüglich der Rauschbreite.

3. Wichtige Beiträge und Ergebnisse

Die Autoren leiten Algorithmen ab, die die Entscheidungsschwierigkeit (Decisional Problem) für sparse LWE und LPN über Moduli $q$ lösen.

Hauptbeiträge:

1. Verallgemeinerung auf $q > 2$: Die Kikuchi-Methode wurde erfolgreich von $\mathbb{Z}_2$ auf $\mathbb{Z}_q$ erweitert, was neue technische Herausforderungen bei der Kodierung von Koeffizienten und der Graphenkonstruktion mit sich brachte.
2. Neue Sample-Time Tradeoffs:
   • Spektrale Methode:
     • Laufzeit: $\tilde{O}(\binom{n}{l} q^l)$
     • Benötigte Stichproben: $m \ge \tilde{O}((\frac{n}{l})^k)$ (für große $q$)
   • q-ary Cover Methode:
     • Laufzeit: $\tilde{O}(\sqrt{\binom{n}{l} q^l} \cdot (n/l)^k)$ (fast quadratische Beschleunigung gegenüber der spektralen Methode).
     • Benötigte Stichproben: Ähnlich wie oben, aber mit besseren Konstanten für bestimmte Parameterbereiche.
3. Quanten-Speedup: Die spektrale Methode lässt sich mit Quantenalgorithmen (ähnlich wie in [SOKB25]) beschleunigen, was zu einer Speedup-Faktor von quadratisch bis quartisch führen kann.

Theoreme (Informell):

• Für Dimension $n$, Stichproben $m \ge \binom{n}{l}^k$ und Parameter $k/2 \le l \le n$ existieren Algorithmen, die das decisionale $k$-sparse LWE/LPN in Zeit $\tilde{O}(\binom{n}{l} q^l)$ lösen.
• Mit der q-ary Cover Methode kann die Zeit auf $\tilde{O}(\sqrt{\binom{n}{l} q^l} \cdot (n/l)^k)$ reduziert werden (unter der Annahme, dass $q$ prim ist).

4. Vergleich mit vorheriger Arbeit (Jain, Lin, Saha [JLS24])

Das Paper setzt sich kritisch mit einer kürzlich erschienenen Arbeit von [JLS24] auseinander, die die Härte von sparse LWE für $k \ge \Omega(\log n)$ und $m = \text{poly}(n)$ vermutet.

• [JLS24] schlugen zwei Angriffe vor (Dense Minor und Sparse Vectors im Kernel), die jedoch bei diesen Parametern exponentielle Laufzeit benötigen.
• Die Autoren zeigen, dass ihre Angriffe die Lücke schließen: Wenn man eine Laufzeit von $2^{\delta n}$ (für beliebig kleines $\delta > 0$) zulässt, reichen bereits polynomiell viele Stichproben aus, um sparse LWE zu brechen, sofern $k$ klein genug ist ($k = O(\log n / \log \log n)$) oder die Stichprobenzahl leicht überpolynomiell ist.
• Dies widerlegt oder zumindest relativiert die Vermutung von [JLS24], dass sparse LWE mit $k \ge \Omega(\log n)$ und polynomiellen Stichproben so hart wie Standard-LWE ist.

5. Bedeutung und Fazit

• Kryptographische Implikationen: Die Ergebnisse zeigen, dass die Verwendung von sparse Vektoren in LWE/LPN über großen Moduli die Sicherheit nicht so stark erhöht wie bisher angenommen, insbesondere wenn eine moderate Erhöhung der Stichprobenzahl oder eine leichte Lockerung der Laufzeitannahmen erlaubt ist.
• Methodischer Fortschritt: Die erfolgreiche Verallgemeinerung der Kikuchi-Methode auf höhere Moduli und die Einführung der q-ary Covers erweitern das Werkzeugset für die Analyse von Lernproblemen mit Rauschen erheblich.
• Praxisrelevanz: Für die Konstruktion von effizienten kryptographischen Schemata (z. B. Fully Homomorphic Encryption) muss bei der Wahl von sparse Parametern nun vorsichtiger agiert werden, da neue Angriffsvektoren identifiziert wurden, die bessere Tradeoffs zwischen Effizienz und Sicherheit aufzeigen.

Zusammenfassend liefert das Paper eine tiefgehende, fine-grained Analyse der Komplexität von sparse LWE/LPN und etabliert neue Grenzen für die Sicherheit dieser Varianten in modernen kryptographischen Anwendungen.