An alternative approach towards attacks against fully-split PLWE instances

Technische Zusammenfassung: Ein alternativer Ansatz gegen Angriffe auf Fully-Split PLWE-Instanzen

Problemstellung
Das Polynomial Learning With Errors (PLWE) Problem ist ein Eckpfeiler der Post-Quanten-Kryptographie und wird aufgrund seiner effizienten algebraischen Eigenschaften oft gegenüber Ring-LWE bevorzugt. Diese Struktur führt jedoch zu potenziellen Schwachstellen. Vorherige Arbeiten, insbesondere [5, 6] und verallgemeinert in [2], führten „wurzelbasierte Angriffe“ ein, die die Existenz spezifischer Polynomfaktoren (bekannt als $n$-ideale Faktoren, $x^n - a$) über endlichen Körpern ausnutzen. Diese Angriffe verwenden Evaluationshomomorphismen und Trace-Operatoren, um PLWE-Proben von Gleichverteilungen zu unterscheiden.

Während [2] diese Angriffe auf Polynome verallgemeinerte, die über Körpererweiterungen faktorisieren, blieb eine kritische offene Frage bestehen: Könnte ein Angreifer das Fehlen verwundbarer Faktoren in einer „sicheren“ PLWE-Instanz umgehen, indem er diese via eines Ringisomorphismus in eine „verwundbare“ Instanz (eine mit geeigneten $n$-idealen Faktoren) abbildet, den Angriff dort durchführt und die Sicherheit der ursprünglichen Instanz schlussfolgert? Diese Arbeit untersucht, ob eine solche Migrationsstrategie via Isomorphismen einen signifikanten Vorteil gegenüber Fully-Split PLWE-Instanzen bietet.

Methodik
Die Autoren verwenden einen rigorosen algebraischen Ansatz, um die Durchführbarkeit des Transfers von PLWE-Proben zwischen verschiedenen Polynomringen zu analysieren. Die Methodik gliedert sich in zwei Hauptphasen:

1. Verallgemeinerung beliebiger Faktorisierung: Die Arbeit untersucht zunächst die Erweiterung wurzelbasierter Angriffe auf Polynome ohne $n$-ideale Faktoren. Unter Verwendung von Lemma 1 zeigen die Autoren, dass Trace-Operatoren über beliebige irreduzible Faktoren definiert werden können. Sie zeigen jedoch, dass die Erfolgswahrscheinlichkeit solcher Angriffe stark von der Anzahl der Null-Koeffizienten des Faktors abhängt, was für beliebige Polynome typischerweise niedrig ist, was den Angriff im allgemeinen Fall unpraktikabel macht.

2. Isomorphie-Analyse in Fully-Split-Settings: Der Kern der Arbeit konzentriert sich auf den „Isomorphie-Ansatz“. Die Autoren betrachten zwei Polynome, $f(x)$ und $g(x)$, die beide vom Grad $N$ und irreduzibel über $\mathbb{Z}[x]$ sind und dieselbe „Faktorisierungsstruktur“ über $\mathbb{F}_q$ teilen (d. h. sie zerlegen sich in irreduzible Faktoren gleicher Grade).

   • Konstruktion: Unter Verwendung des Chinesischen Restsatzes konstruieren sie einen expliziten Isomorphismus $\psi$ zwischen den Ringen $R_q = \mathbb{F}_q[x]/(f(x))$ und $R'_q = \mathbb{F}_q[x]/(g(x))$. Im Fully-Split-Fall (in dem beide Polynome vollständig in lineare Terme zerfallen) wird dieser Isomorphismus durch das Produkt von Vandermonde-Matrizen dargestellt: $\psi = V_g^{-1} \cdot V_f$.
   • Distorsionsanalyse: Die Autoren analysieren die Wirkung der Anwendung dieses Isomorphismus auf PLWE-Proben gefolgt von einer Evaluation an einer Wurzel $\beta$ von $g(x)$. Sie beweisen, dass die resultierende Evaluation mathematisch äquivalent zur Evaluation der ursprünglichen Probe an einer entsprechenden Wurzel $\alpha$ von $f(x)$ ist.
   • Eindeutigkeitsbeweis: Ein wesentlicher Teil der Methodik besteht darin, zu beweisen, dass jeder Ringisomorphismus zwischen solchen Fully-Split-Polynomringen diese spezifische Form annehmen muss (Komposition von Evaluationshomomorphismen und dem konstruierten Isomorphismus). Dies wird durch die Lemmata 2, 3 und 4 sowie Theorem 1 etabliert.

Wesentliche Beiträge

• Formale Beweisführung der Isomorphie-Invarianz: Die Arbeit liefert einen formalen Beweis dafür, dass bei Fully-Split PLWE-Instanzen jeder Versuch, Proben über einen Ringisomorphismus in ein verwundbares Setting zu migrieren, keine neuen Schwachstellen schafft. Das durch den Isomorphismus eingeführte Rauschen (Fehler) verzerrt die Proben so, dass die resultierenden Unterscheidbarkeitsbedingungen identisch mit denen der ursprünglichen Instanz sind.
• Charakterisierung von Ringisomorphismen: Die Autoren charakterisieren die vollständige Menge der Isomorphismen zwischen Fully-Split-Polynomringen und zeigen, dass diese eindeutig durch die Abbildung der Wurzeln bestimmt sind. Dies beweist, dass kein „verborgener“ Isomorphismus existiert, der die Rauschverzerrung umgehen könnte.
• Erweiterung auf beliebige Faktorisierung: Die Arbeit stellt klar, dass, obwohl wurzelbasierte Angriffe theoretisch auf Polynome ohne $n$-ideale Faktoren angewendet werden können, der Mangel an strukturellen Beschränkungen (insbesondere die Anzahl der Null-Koeffizienten) deren Erfolgswahrscheinlichkeit massiv einschränkt, was die Generalisierung als praktische Bedrohung effektiv ausschließt.

Ergebnisse

• Rauschverzerrung: Die Anwendung eines Isomorphismus $\psi$ gefolgt von einer Evaluation an einer Wurzel $\beta$ von $g(x)$ ergibt den Ausdruck $b(\beta) = \sum a_j \alpha^j$, wobei $\alpha$ die entsprechende Wurzel von $f(x)$ ist. Dies zeigt, dass der Angriff auf das transformierte Setting mathematisch identisch mit dem Angriff auf das ursprüngliche Setting ist.
• Scheitern der Migrationsstrategie: Die Analyse bestätigt, dass wenn ein wurzelbasierter Angriff auf die ursprüngliche PLWE-Instanz fehlschlägt (aufgrund von hohem Rauschen oder mangelnder Unterscheidbarkeit), er auch auf jeder isomorphen Instanz fehlschlagen wird. Der Isomorphismus „reinigt“ das Rauschen nicht, sondern bewahrt die zugrunde liegende Schwierigkeit des Problems.
• Spezifische Wurzelanalyse: Die Arbeit analysiert spezifische Fälle, in denen die Evaluationswurzel $\beta$ gleich $0$, $1$ oder eine beliebige Wurzel ist. In allen Fällen reduziert sich die Evaluation auf die Evaluation des ursprünglichen Polynoms an einer entsprechenden Wurzel, was bestätigt, dass kein Vorteil gewonnen wird.

Bedeutung
Die Arbeit kommt zu dem Schluss, dass die Intuition bezüglich der Sicherheit von Fully-Split PLWE-Instanzen korrekt ist: Wenn wurzelbasierte Angriffe gegen eine initiale PLWE-Instanz erfolglos sind, bleiben sie auch dann erfolglos, wenn die Proben über Ringisomorphismen in ein potenziell schwächeres PLWE-Setting transferiert werden.

Dieses Ergebnis liefert eine Quelle des Vertrauens in die Sicherheit von Fully-Split PLWE-Instanzen, die aufgrund ihrer Effizienz (z. B. durch Number Theoretic Transforms) in kryptographischen Konstruktionen häufig verwendet werden. Die Arbeit schließt die „Isomorphie-Migration“ effektiv als praktikablen Vektor aus, um neue Angriffe gegen diese spezifischen Instanzen zu generieren. Die Autoren merken an, dass diese Analyse spezifisch für Fully-Split-Polynome ist, aber den Großteil der kryptographisch relevanten PLWE-Instanzen abdeckt. Die Arbeit beansprucht nicht, die Sicherheit von Nicht-Fully-Split-Instanzen oder andere Angriffsvektoren (wie die in der Einleitung erwähnten Stickelberger-Ideal-Angriffe) zu lösen, sondern festigt vielmehr das Verständnis wurzelbasierter Angriffe innerhalb des Fully-Split-Bereichs.