🔢 mathematics

Cryptanalysis of the Legendre Pseudorandom Function over Extension Fields

Diese Arbeit präsentiert die erste umfassende Kryptoanalyse der Legendre-Pseudorandom-Funktion über Erweiterungskörper, indem sie neue Angriffsvektoren unter passiven und aktiven Bedrohungsmodellen aufzeigt und beweist, dass nur Varianten mit einem höheren Schlüsselgrad (d ≥ 2) eine exponentielle Sicherheit gewährleisten können.

Ursprüngliche Autoren: Daksh Pandey

Veröffentlicht 2026-04-07

📖 4 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Daksh Pandey

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

🛡️ Der Legendre-Code: Warum der einfache Schlüssel in der Erweiterung versagt

Stell dir vor, du hast einen sehr cleveren, aber einfachen Tresor (den Legendre-Pseudozufallsgenerator oder PRF). Dieser Tresor ist besonders beliebt, weil er extrem schnell zu öffnen ist, wenn man ihn mit vielen Leuten gleichzeitig benutzt (in der Kryptografie nennt man das Multi-Party Computation oder Zero-Knowledge Proofs).

Bisher war dieser Tresor sicher, solange man ihn in einer einfachen Welt (den sogenannten Primfeldern) benutzte. Aber die Entwickler wollten ihn noch schneller machen und haben ihn in eine komplexere, größere Welt verschoben: die Erweiterungsfelder.

Das Problem? In dieser neuen, größeren Welt hat sich herausgestellt, dass der Tresor eigentlich ein Loch im Boden hat. Das ist genau das, was dieses Papier aufdeckt.

Hier ist die Geschichte in drei Teilen:

1. Der Versuch, den Tresor zu verstecken (Die "Keine-Carry"-Fraktur)

In der alten Welt (Primfelder) zählten die Zahlen einfach hoch: 1, 2, 3, 4... Wenn man eine Zahl addierte, "trug" man den Überlauf immer weiter (wie bei 9 + 1 = 10). Hacker nutzten diese Vorhersehbarkeit aus, um den Tresor zu knacken.

Als man den Tresor in die neue Welt (Erweiterungsfelder) brachte, änderten die Entwickler die Regeln:

Die neue Regel: Wenn du eine Zahl addierst, gibt es keinen Überlauf mehr.
Der Vergleich: Stell dir vor, du hast 3 Regale mit jeweils 10 Fächern. In der alten Welt, wenn du im letzten Fach (Fach 10) noch einen Stein hinzufügst, wandert er ins erste Fach des nächsten Regals. In der neuen Welt passiert das nicht. Der Stein bleibt einfach liegen, und das Fach daneben bleibt leer.

Die Entwickler dachten: "Super! Da die Zahlen nicht mehr fließend verbunden sind, können Hacker keine Muster mehr erkennen. Wir sind sicher!"

2. Der passive Angriff: Das Muster im Chaos (Die "Differential-Signatur")

Der Autor des Papers, Daksh Pandey, sagt: "Nicht so schnell."

Auch wenn die Zahlen nicht mehr fließen, ist das Muster, wie sie sich verhalten, vorhersehbar.

Die Analogie: Stell dir vor, du hast eine Reihe von Musiknoten. In der alten Welt war es eine glatte Melodie. In der neuen Welt sind die Noten unterbrochen (die "Fraktur"). Aber die Art und Weise, wie sie unterbrochen sind, wiederholt sich in einem festen Rhythmus.
Der Hack: Der Angreifer nutzt eine neue Technik namens "Differential Signature" (Unterschieds-Signatur). Er gruppiert die unterbrochenen Musikstücke nach ihrer Form.
- "Ah, diese Unterbrechung sieht aus wie ein 'V'. Diese andere wie ein 'A'."
- Sobald er die Formen gruppiert hat, kann er den geheimen Schlüssel trotzdem erraten, indem er nur die richtigen Gruppen vergleicht. Es ist wie ein Detektiv, der nicht die ganze Spur verfolgt, sondern nur die Fußabdrücke nach ihrer Form sortiert, um den Täter zu finden.

Ergebnis: Der Tresor ist auch ohne aktive Eingriffe (nur durch Beobachten) zu knacken.

3. Der aktive Angriff: Der Geometrie-Trick (Die "Multiplikative Homomorphie")

Was, wenn der Hacker nicht nur zuschaut, sondern aktiv fragt?

Der Trick: Statt die Zahlen einfach hochzuzählen (Addition), fragt der Hacker nach Zahlen, die sich wie eine geometrische Folge verhalten (Multiplikation).
Die Analogie: Stell dir vor, der Tresor ist ein Schloss, das auf Addition nicht reagiert. Aber der Hacker dreht am Schlüssel in einer bestimmten, sich wiederholenden Kreisbewegung.
Das Ergebnis: Durch diese spezielle Art des Fragens (eine "geometrische Sequenz") funktioniert die Mathematik plötzlich wieder perfekt. Die Unterbrechungen verschwinden, und der Schlüssel lässt sich direkt berechnen.
Die Geschwindigkeit: Dieser Angriff ist so effizient, dass er den Schlüssel fast sofort findet. Es ist, als würde man einen Code knacken, indem man einfach die richtige Drehrichtung wählt, anstatt alle Kombinationen durchzuprobieren.

4. Die Lösung: Mehr Komplexität (Höhere Grade)

Wenn der einfache Schlüssel (ein Polynom vom Grad 1) so leicht zu knacken ist, was tun?

Die Lösung: Man muss den Schlüssel komplexer machen. Statt nur einer Zahl, nutzt man ein Polynom höheren Grades (z. B. mit $x^2$ , $x^3$ usw.).
Warum das hilft: Bei diesen komplexeren Schlüsseln funktioniert der "Geometrie-Trick" nicht mehr. Die Mathematik lässt sich nicht mehr so einfach in einen einfachen Code zerlegen.
Die Empfehlung: Für echte Sicherheit in der neuen Welt (Erweiterungsfelder) muss man mindestens Grad 2 oder besser Grad 3 oder 4 verwenden. Nur dann ist der Tresor wirklich sicher.

📝 Fazit in einem Satz

Der einfache Legendre-Code, den man in die komplexere Welt der Erweiterungsfelder gebracht hat, ist wie ein Haus mit einer Tür, die man für sicher hielt, weil sie krumm war – aber ein Dieb hat herausgefunden, dass man sie trotzdem mit einem einfachen Trick öffnen kann. Um sicher zu sein, muss man die Tür durch eine massive, komplexe Banktresor-Tür ersetzen (höherer Polynomgrad).

Wichtig: Dieser Code ist für die Zukunft der Kryptografie (MPC und ZKP) wichtig, weil viele Systeme versuchen, diesen schnellen Code zu nutzen. Dieses Papier warnt: Nutzt nicht die einfache Version, sonst ist alles unsicher!

Titel: Kryptoanalyse der Legendre-Pseudorandom-Funktion über Erweiterungskörpern

Autor: Daksh Pandey (Indian Institute of Technology, Roorkee)

1. Problemstellung

Die Legendre-Pseudorandom-Funktion (PRF) ist eine effiziente kryptografische Primitive, die auf dem Legendre-Symbol basiert und zunehmend in Multi-Party-Computation (MPC) und Zero-Knowledge-Proof (ZKP) Protokollen eingesetzt wird, da sie eine geringe multiplikative Komplexität aufweist. Während die Sicherheit der Legendre-PRF über Primkörpern ( $\mathbb{F}_p$ ) gut untersucht ist, hat sich der Fokus in jüngster Zeit auf ihre Instantiierung über Erweiterungskörpern ( $\mathbb{F}_{p^r}$ ) verschoben, um den Durchsatz in bestimmten Protokollen zu optimieren.

Das zentrale Problem dieser Arbeit ist die Sicherheitsbewertung der einzelgradigen Legendre-PRF ( $d=1$ ) über Erweiterungskörpern. Es wird untersucht, ob die strukturellen Eigenschaften von Polynom-Eingaben über $\mathbb{F}_{p^r}$ (insbesondere das Fehlen von Überträgen bei der Addition) ausreichen, um bekannte Angriffe wie Kollisionsangriffe zu neutralisieren, oder ob neue, effiziente Angriffsvektoren existieren.

2. Methodik und Grundlagen

Die Arbeit analysiert die PRF unter zwei Bedrohungsmodellen:

Passives Modell: Der Angreifer beobachtet einen Schlüsselstrom, der durch sequentielle additive Zählerabfragen ( $n, n+1, n+2, \dots$ ) generiert wird.
Aktives Modell (Chosen-Query): Der Angreifer kann beliebige Eingaben an die PRF senden.

Mathematische Grundlagen:

Polynom-Enkodierung: Ganzzahlige Zähler werden in Polynome über $\mathbb{F}_{p^r}$ umgewandelt. Im Gegensatz zur Integer-Arithmetik erfolgt die Addition in $\mathbb{F}_{p^r}$ koeffizientenweise ohne Übertrag ("no-carry").
Verallgemeinertes Legendre-Symbol: Die Ausgabe wird durch Exponentiation ( $A(x)^{(p^r-1)/2}$ ) bestimmt, wobei $+1$ und $-1$ auf Binärwerte $0$ und $1$ abgebildet werden.

3. Schlüsselbeiträge und Angriffsvektoren

A. Passive Kryptoanalyse: "Differential Signatures" und "No-Carry Fracture"

Der Autor zeigt, dass die erwartete Sicherheit durch das Fehlen von Überträgen ("no-carry fracture") trügerisch ist.

Strukturelle Beobachtung: Bei sequentiellen Abfragen ( $n \to n+1$ ) ist die Differenz $\Delta_n$ in $\mathbb{F}_{p^r}$ nicht konstant (wie bei $1$ in $\mathbb{F}_p$ ), sondern variiert periodisch basierend auf der $p$ -adischen Bewertung von $n$ . Dies zerbricht die kontinuierliche arithmetische Progression, die klassische Kollisionsangriffe benötigen.
Neuer Angriff: Trotz dieser Fragmentierung ist die Folge der Differenzen deterministisch und periodisch. Der Autor führt eine "Differential Signature"-Bucketing-Technik ein.
- Der Angreifer gruppiert Fenster des Schlüsselstroms basierend auf ihrer strukturellen Form (der Sequenz der Differenzen).
- Durch das Clustern dieser "gebrochenen" Sequenzen kann der Angreifer die Abhängigkeit von der kontinuierlichen Addition umgehen.
- Ergebnis: Passive Wiederherstellung des geheimen Schlüssels $K$ mit einer Komplexität von $O(U \cdot p^r / M)$ , wobei $U$ die Eindeutigkeitsdistanz und $M$ die Anzahl der beobachteten Bits ist.

B. Aktive Kryptoanalyse: Geometrische Sequenzen

Unter einem aktiven Bedrohungsmodell (Chosen-Query) lässt sich die additive Fragmentierung vollständig umgehen.

Strategie: Der Angreifer fragt die PRF nicht mit einer arithmetischen, sondern mit einer geometrischen Sequenz ab, generiert durch ein primitives Polynom $g(x)$ (d.h. Eingaben $g^i$ ).
Homomorphismus-Ausnutzung: Das verallgemeinerte Legendre-Symbol ist multiplikativ. Dies ermöglicht eine Faktorisierung der Auswertung:
$L(g^i + K) = L(K) \cdot L(g^{i+j} + 1)$
Dabei ist $j$ ein diskreter Logarithmus, der den Schlüssel $K$ repräsentiert.
Verallgemeinerter Kollisionsangriff: Durch diese algebraische Reduktion wird das Problem auf einen reinen Verschiebungswert (Shift) reduziert. Der Angreifer kann den State-of-the-Art-Tabelle-Kollisionsangriff direkt auf die multiplikative Gruppe anwenden.
- Ergebnis: Vollständige Extraktion des Schlüssels $K$ in $O(p^r / M)$ Operationen. Dies ist eine signifikante Verbesserung gegenüber dem passiven Angriff und zeigt, dass die additive Sicherheit irrelevant ist, wenn der Angreifer die multiplikative Struktur ausnutzen kann.

4. Ergebnisse und Sicherheitsgrenzen

Bruch der $d=1$ Variante: Die Arbeit beweist, dass die einstufige Legendre-PRF ( $d=1$ ) über Erweiterungskörpern sowohl unter passiven als auch unter aktiven Modellen fundamental unsicher ist. Die "no-carry"-Eigenschaft bietet keinen ausreichenden Schutz gegen strukturelle Reduktionen.
Notwendigkeit höherer Grade: Um Sicherheit zu gewährleisten, müssen höhere Grade ( $d \ge 2$ $d \geq 2$ ) verwendet werden.
- Bei $d \ge 2$ (z.B. quadratische Polynome $x^2 + K_1x + K_0$ ) lässt sich der Ausdruck nicht mehr in eine konstante Verschiebung und eine universelle Referenzfolge faktorisieren.
- Der geometrische Angriff wird dadurch neutralisiert, da die Koeffizienten nicht mehr sauber isoliert werden können.
- Empfehlung: Für eine exponentielle Sicherheitsmarge gegen strukturelle Reduktionen sollten Grade $d \ge 3$ oder $d \ge 4$ verwendet werden, da selbst $d=2$ anfällig für optimierte Meet-in-the-Middle-Angriffe sein könnte.

5. Bedeutung und Fazit

Diese Studie liefert die erste umfassende Kryptoanalyse der Legendre-PRF über Erweiterungskörpern. Sie widerlegt die Annahme, dass die Verschiebung von Primkörpern zu Erweiterungskörpern allein durch die Unterbrechung der additiven Kette ausreichend Sicherheit bietet.

Praktische Implikation: Implementierungen der Legendre-PRF in MPC- und ZKP-Systemen, die Erweiterungskörper nutzen, müssen dringend auf höhergradige Schlüsselvarianten ( $d \ge 2$ ) umstellen, um nicht durch algebraische Angriffe kompromittiert zu werden.
Theoretischer Beitrag: Die Arbeit etabliert formale Grenzen für die Sicherheit von PRFs in Erweiterungskörpern und zeigt, wie algebraische Homomorphismen (hier multiplikativ) genutzt werden können, um scheinbar robuste additive Barrieren zu durchbrechen.

Der Quellcode für die beschriebenen Angriffe ist als Open-Source auf GitHub verfügbar, was die Reproduzierbarkeit und weitere Forschung fördert.