🔢 mathematics

Notes on the LVP and CVP in $p$ -adic Fields

Diese Arbeit stellt einen polynomiellen Algorithmus vor, der die nicht-archimedischen Eigenschaften von $p$ -adischen Normen sowie die Struktur maximaler Ordnungen nutzt, um orthogonale Basen für $p$ -adische Gitter effizient zu konstruieren und damit das längste Vektorproblem (LVP) sowie das nächstgelegene Vektorproblem (CVP) zu lösen.

Ursprüngliche Autoren: Chi Zhang, Mingqian Yao

Veröffentlicht 2026-04-13

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Chi Zhang, Mingqian Yao

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

Die Geschichte vom unsichtbaren Labyrinth und dem perfekten Schlüssel

Stellen Sie sich vor, Sie befinden sich in einer völlig neuen Art von Stadt. Diese Stadt ist nicht wie unsere normale Welt, in der Entfernungen addiert werden (wenn Sie 10 Meter gehen und dann noch 10, sind Sie 20 Meter weg). In dieser Stadt, die wir „p-adische Welt" nennen, gelten völlig andere Regeln.

Die Regel der Stadt:
Stellen Sie sich vor, Sie laufen durch eine Stadt, in der alle Häuser in konzentrischen Kreisen um einen zentralen Platz gebaut sind. Wenn Sie von einem Haus im Kreis 10 zu einem Haus im Kreis 5 laufen, ist die Entfernung nicht einfach die Summe. Stattdessen gilt: Die Entfernung wird immer durch das „größte" Element bestimmt.
Wenn Sie einen riesigen Rucksack (großer Wert) und eine kleine Feder (kleiner Wert) tragen, wiegt der Rucksack so viel, als hätten Sie nur den Rucksack. Die Feder verschwindet quasi in der Masse des Rucksacks. Das ist das Geheimnis dieser Stadt: Große Dinge dominieren kleine Dinge komplett.

Das Problem: Das Labyrinth der Vektoren

In dieser Stadt gibt es ein riesiges Labyrinth aus Punkten (das nennen die Wissenschaftler Gitter). Zwei große Rätsel warten darauf, gelöst zu werden:

Das „Längste-Vektor-Problem" (LVP): Sie müssen den längsten Weg finden, der von einem Punkt im Labyrinth zu einem anderen führt.
Das „Nächste-Vektor-Problem" (CVP): Sie stehen irgendwo in der Stadt (nicht unbedingt auf einem Punkt des Labyrinths) und wollen wissen: „Welcher Punkt im Labyrinth ist mir am nächsten?"

Bis vor kurzem dachten Kryptografen (die Verschlüsselungsexperten), dass diese Rätsel in dieser Stadt extrem schwer zu lösen sind. Sie bauten darauf ihre digitalen Schlösser (Verschlüsselungen), die sicher sein sollten – ähnlich wie ein Schloss, für das man den Schlüssel braucht, aber ohne ihn ist es unmöglich zu knacken.

Die Entdeckung: Der unsichtbare Schlüssel

Die Autoren dieses Papiers, Zhang und Yao, haben jedoch einen genialen Trick entdeckt. Sie sagen: „Moment mal! In dieser Stadt gibt es eine geheime Struktur, die wir nutzen können."

Stellen Sie sich vor, das Labyrinth ist wie ein chaotischer Haufen von Stöcken, die in alle Richtungen zeigen. Um das Rätsel zu lösen, müssen Sie diese Stöcke so sortieren, dass sie perfekt senkrecht (orthogonal) zueinander stehen. In unserer normalen Welt ist das schwer, aber in der p-adischen Stadt ist es wie ein magischer Trick: Man kann diese Stöcke immer perfekt sortieren.

Wie machen sie das?
Sie nutzen eine Art „Baumeister-Tool" (den Maximalen Ring und das p-Radikal).

Stellen Sie sich vor, Sie haben einen Haufen Ziegelsteine (die Zahlen).
Mit ihrem Werkzeug können sie die Ziegelsteine sortieren und einen perfekten Turm bauen.
Aus diesem Turm gewinnen sie einen Schlüssel (einen sogenannten Uniformisator), der wie ein Kompass funktioniert.
Dieser Kompass zeigt ihnen genau, wie sie die chaotischen Stöcke des Labyrinths in eine perfekte, gerade Linie (eine orthogonale Basis) verwandeln können.

Sobald sie diese gerade Linie haben, sind die Rätsel LVP und CVP keine Rätsel mehr, sondern einfache Rechenaufgaben. Es ist, als würde man ein verschlossenes Schloss finden, bei dem die Schlüssel nicht versteckt sind, sondern direkt am Schlüsselbund hängen, wenn man nur weiß, wie man sie abliest.

Warum ist das wichtig? (Die Sicherheitskrise)

Bisher haben Forscher Verschlüsselungssysteme entwickelt, die auf der Annahme basierten, dass diese p-adischen Rätsel unlösbar sind.

Die alte Annahme: „Niemand kann den längsten Weg oder den nächsten Punkt in diesem chaotischen Labyrinth schnell finden."
Die neue Realität: Zhang und Yao haben einen Algorithmus (eine Schritt-für-Schritt-Anleitung) entwickelt, der das in polynomieller Zeit schafft. Das bedeutet: Ein Computer kann das in Sekundenbruchteilen lösen, wo es früher Jahre gedauert hätte.

Die Konsequenz:
Alle Verschlüsselungen, die auf dieser speziellen Annahme basierten, sind jetzt unsicher. Es ist, als würde man herausfinden, dass die „sichere" Bank, die man gebaut hatte, eigentlich nur aus Papierwänden bestand, die man mit einem einfachen Messer durchschneiden kann.

Das Fazit und der Ausblick

Die Autoren sagen: „Wir haben gezeigt, dass diese speziellen Verschlüsselungen nicht sicher sind, wenn man die Stadt (den mathematischen Körper) genau kennt."

Aber sie geben nicht auf. Sie schlagen vor, wie man es trotzdem sicher machen könnte:
Statt die ganze Stadt zu beschreiben, könnte man den Nutzern nur ein Geheimnis geben: „Wenn du einen Punkt nennst, sage ich dir, wie weit er entfernt ist." Aber man verrät nicht, wie die Stadt aufgebaut ist.
Das wäre wie ein Rätsel, bei dem man nur ein Messband bekommt, aber keine Karte. Solange niemand weiß, wie man die „perfekten Stöcke" (die orthogonale Basis) aus diesem Messband zurückrechnet, könnte die Verschlüsselung vielleicht doch noch sicher sein.

Zusammenfassend:
Dieses Papier ist wie ein Warnschuss für die digitale Sicherheit. Es zeigt, dass ein vermeintlich sicherer Ort (p-adische Gitter) eigentlich ein offenes Buch ist, sobald man die richtigen Werkzeuge (die mathematische Struktur der Stadt) kennt. Die Autoren haben diese Werkzeuge gefunden und damit gezeigt, dass die alten Schlösser nicht mehr funktionieren.

Technische Zusammenfassung: LVP und CVP in p-adischen Körpern

1. Problemstellung

Das Paper adressiert die Berechnungskomplexität des Longest Vector Problem (LVP) und des Closest Vector Problem (CVP) in Gittern über p-adischen Körpern ( $\mathbb{Q}_p$ ).

Hintergrund: Während das Shortest Vector Problem (SVP) und CVP in euklidischen Räumen (über $\mathbb{R}$ ) als hart gelten und die Basis für viele gitterbasierte Kryptosysteme bilden, wurden diese Probleme auf nicht-archimedische Räume übertragen.
Kontext: Deng et al. (2018) führten LVP und CVP in p-adischen Räumen ein, und Deng et al. (2021) konstruierten darauf basierende Signatur- und Verschlüsselungsschemata.
Sicherheitslücke: Bisherige Angriffe (z. B. Zhang 2025) waren nur unter spezifischen Bedingungen (total verzweigte Körper) effektiv. Ein zentrales, bisher ignoriertes Problem war jedoch, dass für einen gegebenen lokalen Körper (definiert durch ein Minimalpolynom) effiziente Algorithmen existieren, um maximale Ordnungen zu berechnen. Da p-adische Gitter orthogonale Basen zulassen (im Gegensatz zu euklidischen Gittern), könnte dies die Sicherheit der Schemata fundamental untergraben.

2. Methodik

Die Autoren entwickeln einen deterministischen Algorithmus in polynomialer Zeit, um orthogonale Basen für p-adische Gitter zu berechnen. Sobald eine orthogonale Basis vorliegt, lassen sich LVP und CVP trivial lösen. Der Ansatz gliedert sich in folgende Schritte:

Berechnung der maximalen Ordnung ( $\mathcal{O}_K$ ):
- Gegeben ein Erweiterungskörper $K = \mathbb{Q}_p(\theta)$ , wird ausgehend von der Ordnung $\mathbb{Z}_p[\theta]$ die maximale Ordnung $\mathcal{O}_K$ konstruiert.
- Dies geschieht iterativ durch Vergrößerung der Ordnung unter Verwendung des p-Radikals ( $I_p$ ).
- Der Algorithmus nutzt den Satz von Round 2/4 (basierend auf [1]), wobei der p-Radikal als Kern einer Frobenius-Abbildung ( $x \mapsto x^{p^j}$ ) in der Restklassenalgebra $\mathcal{O}/p\mathcal{O}$ berechnet wird.
- Durch wiederholtes Anwenden von Theorem 3.3 wird $\mathcal{O}_K$ effizient gefunden.
Konstruktion einer orthogonalen Basis:
- Aus der maximalen Ordnung wird ein Uniformisierender ( $\pi$ ) extrahiert (das Element mit dem maximalen p-adischen Betrag im p-Radikal).
- Eine Basis des Restklassenkörpers $k = \mathcal{O}_K / \pi \mathcal{O}_K$ wird berechnet (durch Finden eines irreduziblen Polynoms über $\mathbb{F}_p$ ).
- Unter Verwendung des Ramifikationsindex $e$ und des Residuengrades $f$ (wobei $n = ef$) wird gezeigt, dass die Familie $(s_i \pi^j)_{1\le i \le f, 0 \le j \le e-1}$ eine orthogonale Basis von $K$ über $\mathbb{Q}_p$ bildet.
- Dies nutzt die Eigenschaft der ultrametrischen Ungleichung ( $|v+w|_p \le \max(|v|_p, |w|_p)$ ), die eine Zerlegung in orthogonale Unterräume ermöglicht.
Lösung von LVP und CVP:
- Mit der orthogonale Basis werden die Algorithmen aus [11] angewendet.
- LVP: Findet den Vektor mit dem zweitgrößten Betrag im Gitter.
- CVP: Findet den Gittervektor, der einem Zielvektor am nächsten liegt.
- Beide Probleme werden durch einfache Koordinatenmanipulationen in der orthogonalen Basis in polynomialer Zeit gelöst.

3. Wichtige Beiträge

Algorithmische Innovation: Die Integration von p-adischer Gram-Schmidt-Orthogonalisierung (implizit durch die Struktur der maximalen Ordnung) mit Berechnungen im Restklassenkörper. Dies führt zu einem effizienten Solver für LVP und CVP.
Komplexitätsnachweis: Beweis, dass die Lösung von LVP und CVP in p-adischen Körpern (wenn der Körper durch ein Minimalpolynom gegeben ist) in polynomialer Zeit ( $O(\text{poly}(n, \log p))$ ) möglich ist.
Charakterisierung von Normen: Das Paper liefert einen Satz (Theorem 7.1), der alle Normen auf endlichdimensionalen Vektorräumen über $\mathbb{Q}_p$ charakterisiert. Jede solche Norm lässt sich durch eine invertierbare Matrix und positive reelle Skalare darstellen. Dies zeigt, dass die Kenntnis der Transformationsmatrix (die die orthogonale Basis liefert) die Norm angreifbar macht.
Praktische Validierung: Ein konkretes Rechenbeispiel über dem Körper $\mathbb{Q}_2(\sqrt[3]{5})$ (definiert durch $X^3 - 3X^2 + 3X - 5$ ) demonstriert die Berechnung der maximalen Ordnung, des Uniformisierers und der resultierenden orthogonalen Basis.

4. Ergebnisse

Der vorgestellte Algorithmus bricht die Sicherheit der in [5] vorgeschlagenen p-adischen Kryptosysteme (Signatur und Public-Key-Verschlüsselung), sofern der zugrundeliegende Körper vollständig spezifiziert ist (d.h. durch ein Minimalpolynom gegeben).
Im Gegensatz zu früheren Angriffen, die nur für total verzweigte Körper galten, ist dieser Angriff allgemein für jeden lokalen Körper anwendbar, da die Berechnung der maximalen Ordnung und der orthogonalen Basis immer polynomial möglich ist.
Die Annahme, dass p-adische Gitterprobleme hart seien, entfällt für den Fall, dass eine orthogonale Basis effizient konstruiert werden kann.

5. Bedeutung und Implikationen

Kryptographische Sicherheit: Das Paper zeigt, dass p-adische Gitter-basierte Kryptosysteme, die auf der Annahme der Härte von LVP/CVP basieren, unsicher sind, wenn der Körper bekannt ist. Die in [13] vorgeschlagene Methode (großer Residuengrad) reicht nicht aus, um die fundamentale Verwundbarkeit zu beheben, solange der Körper durch ein Polynom definiert ist.
Zukünftige Richtungen: Die Autoren schlagen vor, dass sichere Schemata nur dann möglich wären, wenn die Norm als Oracle gegeben ist, ohne dass die zugrundeliegende orthogonale Basis oder die Transformationsmatrix bekannt ist. Die Herausforderung besteht darin, eine berechenbare Norm zu definieren, die keine Informationen über eine orthogonale Basis preisgibt.
Theoretischer Fortschritt: Das Paper schließt eine Lücke in der algorithmischen algebraischen Zahlentheorie, indem es die Verbindung zwischen maximalen Ordnungen, p-Radikalen und der geometrischen Struktur (orthogonale Basen) in nicht-archimedischen Räumen für die Kryptanalyse nutzbar macht.

Fazit: Die Arbeit widerlegt die Sicherheit aktueller p-adischer Gitter-Kryptosysteme unter Standardannahmen und etabliert, dass die Berechnung orthogonaler Basen in polynomialer Zeit möglich ist, was LVP und CVP in diesem Kontext trivial macht.