⚡ electrical engineering

Deterministic Johnson--Lindenstrauss Projections from Pisot $\beta$ -Transformations for Zero-Knowledge Private Routing

Dieses Paper führt eine deterministische, Zero-Knowledge-freundliche Johnson–Lindenstrauss-Projektion ein, die aus Pisot- $\beta$ -Transformationen abgeleitet ist und die Notwendigkeit kostspieliger In-Circuit-Zufälligkeit durch die Verwendung eines einzigen öffentlichen Seeds eliminiert, um eine dimensionsfreie Varianz sowie exakte Reproduzierbarkeit in endlichen Körpern zu erreichen und gleichzeitig paarweise Abstände zu bewahren.

Ursprüngliche Autoren: I. Dey, I. Cherkaoui

Veröffentlicht 2026-08-14

📖 7 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: I. Dey, I. Cherkaoui

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

Stellen Sie sich eine Welt vor, in der Ihr digitales Leben aus einer Serie geheimer Handschläge besteht. Sie möchten einem Türsteher beweisen, dass Sie zu einem VIP-Club gehören, ohne Ihren Ausweis zu zeigen, oder einer Bank beweisen, dass Sie genug Geld haben, ohne Ihren Kontostand offenzulegen. Das ist die Magie von „Zero-Knowledge Proofs“ (ZK): eine Art zu sagen: „Ich kenne das Geheimnis“, ohne das Geheimnis selbst zu flüstern. Aber hier ist der Haken: Um zu beweisen, dass Sie zur richtigen Gruppe gehören, ist Ihre digitale Identität oft eine massive, komplexe Wolke aus Zahlen (ein hochdimensionaler Vektor). Zu prüfen, ob diese Wolke mit der VIP-Liste übereinstimmt, ist wie der Versuch, ein bestimmtes Sandkorn in einem Berg zu finden; es verbraucht so viel Rechenleistung und Zeit, dass es alles verlangsamt.

Um dies zu beheben, nutzen Wissenschaftler einen Trick namens „Johnson-Lindenstrauss“ (JL)-Projektion. Stellen Sie sich das wie einen magischen Fotokopierer vor, der eine riesige, 3D-Skulptur in einen flachen, 2D-Schatten zusammendrückt. Erstaunlicherweise bleiben, wenn man die Skulptur genau richtig zusammendrückt, die Abstände zwischen den Punkten im Schatten exakt dieselben wie im Original. Dies macht die Aufgabe des „Türstehers“ einfach und schnell. Es gibt jedoch einen Haken: Die Standardmethode, um diese Quetschmaschine zu bauen, besteht darin, einen digitalen Würfel zu werfen. Die Maschine ist zufällig, also müssen Sie beweisen, dass Sie den Würfel korrekt geworfen haben, um zu beweisen, dass Sie nicht vom Protokoll abgewichen sind. Dieser Beweis ist so schwerfällig, dass er die gesamte Geschwindigkeit zunichtemacht, die Sie durch das Zusammendrücken der Daten gewonnen haben. Wir brauchen eine Quetschmaschine, die feststehend, öffentlich und ohne Würfelwurf ist, um ihre Fairness zu beweisen.

Dieses Paper stellt einen neuen Weg vor, um diese Maschine unter Verwendung einer speziellen Art von Mathematik namens „Pisot $\beta$ -Transformationen“ zu bauen. Die Autoren, I. Dey und I. Cherkaoui, haben eine deterministische (nicht-zufällige) Projektion konstruiert, die genauso gut funktioniert wie die zufälligen, aber für jeden überall perfekt reproduzierbar ist, ohne dass ein Zufallssamen (Random Seed) nachgewiesen werden muss.

Das Problem: Der „Zufalls“-Engpass

In der Welt des privaten Routings – wo ein KI-Agent entscheidet, welches Expertenmodell eine private Nachricht bearbeiten soll – wird die Nachricht in eine lange Liste von Zahlen umgewandelt. Um die Privatsphäre zu wahren, beweist der Agent, dass die Nachricht zu einer „sicheren“ Kategorie gehört, indem er sie mit einer Liste bekannter „Zentroiden“ (Durchschnittsbeispielen für sichere Nachrichten) vergleicht. Dieser Vergleich ist teuer.

Die übliche Lösung ist es, die Liste der Zahlen mithilfe einer Zufallsmatrix zu verkleinern (die JL-Projektion). Da die Matrix jedoch zufällig ist, muss der Computer sich auf sie festlegen und beweisen, dass sie fair generiert wurde. Dieser Beweis ist so kostspielig, dass er den Zweck der Datenverkleinerung eigentlich schon wieder zunichtemacht. Die Autoren argumentieren, dass wir eine Matrix benötigen, die öffentlich, feststehend und für alle identisch ist, damit kein Beweis für die Zufälligkeit nötig ist.

Die Lösung: Die „Streck-und-Falt“-Maschine

Die Autoren schlagen vor, diese feste Matrix mithilfe einer chaotischen Abbildung namens Pisot $\beta$ -Transformation zu bauen.

Die Analogie: Stellen Sie sich ein Stück Teig vor. Sie strecken es aus (Multiplikation mit einer Zahl $\beta$ ) und falten es dann wieder auf sich selbst zurück (den Rest bilden). Dies ist ein „chaotischer“ Prozess; wenn man mit zwei fast identischen Punkten aus Teig beginnt, landen sie schnell an völlig unterschiedlichen Orten. Dieses Chaos ist normalerweise großartig, um Daten zu verschleiern, aber schrecklich für Computer, die sich über ein Ergebnis einigen müssen.
Das Problem mit normalem Chaos: Wenn zwei Computer versuchen, dieses Strecken und Falten zu simulieren, können winzige Unterschiede in ihrer Mathematik (wie Rundungsfehler) dazu führen, dass sie schnell divergieren. Ein Computer glaubt vielleicht, der Teig sei an Position A, während ein anderer denkt, er sei an Position B. Sie können sich nicht auf die Matrix einigen.
Die Pisot-Magie: Die Autoren verwenden eine spezielle Art von Zahl, eine sogenannte Pisot-Zahl (wie die Goldene Ratio, 1,618, oder die Plastische Zahl, 1,325). Diese Zahlen besitzen eine besondere algebraische Eigenschaft: Obwohl der Prozess chaotisch ist, kann die „Orbit“ (der Pfad, den der Teig nimmt) exakt mithilfe eines endlichen Satzes von Regeln berechnet werden.
- Das Ergebnis: Zwei Computer können dieselbe „Streck-und-Falt“-Simulation durchführen und das exakt gleiche Ergebnis erhalten, Bit für Bit, ohne Rundungsfehler. Es ist, als hätte man ein Rezept, das perfekt funktioniert, egal ob man einen Holzlöffel oder einen Metalllöffel verwendet, solange man die Schritte befolgt.

Was sie herausgefunden haben

Das Team hat bewiesen, dass diese deterministische Matrix genauso gut funktioniert wie die zufälligen, bietet jedoch einige entscheidende Vorteile:

Es bewahrt Abstände: Sie haben mathematisch bewiesen, dass die „zusammengedrückten“ Daten die Abstände zwischen den Punkten fast exakt so beibehalten wie das Original. Der Fehler (Bias) ist winzig und wird auch nicht größer, wenn die Daten massiv werden.
Es ist schnell und günstig: Da die Matrix feststehend und öffentlich ist, muss der Computer keine Zeit damit verbringen, zu beweisen, dass sie fair generiert wurde. Er nutzt einfach das vorab vereinbarte Rezept.
Es ist reproduzierbar: Sie haben gezeigt, dass eine generische chaotische Abbildung (wie die berühmte „Logistische Abbildung“) eine unmöglich große Menge an Speicher benötigen würde, um exakt berechnet zu werden (exponentielles Wachstum), die Pisot-Abbildung hingegen nur eine winzige, feste Menge an Speicher benötigt (lineares Wachstum).
- Der Test: In ihren Simulationen haben sie ihre Pisot-Methode mit sechs anderen Standardmethoden verglichen, einschließlich zufälliger Gauß-Matrizen und anderer chaotischer Abbildungen.
- Das Ergebnis: Die Pisot-Methode erreichte die statistische Qualität der Zufallsmatrizen perfekt. Das „Rauschen“ in der Messung war identisch, und die Fähigkeit, Nachrichten korrekt zu routen, war absolut gleich. Tatsächlich fanden sie heraus, dass ein einziger öffentlicher „Seed“ (der Startpunkt des Teigs) ausreicht, um die Abstände für alle Paare von Zentroiden in einer großen Liste zu bewahren.

Der Haken (und die Zukunft)

Die Autoren sind sich sehr bewusst darüber, was sie bewiesen haben und was nicht.

Was bewiesen ist: Sie haben mathematisch bewiesen, dass der Bias klein ist und dass die Varianz (das Rauschen) gut kontrolliert wird. Sie haben bewiesen, dass ein guter Seed existiert und durch Suche gefunden werden kann.
Was gemessen wurde: Sie führten Simulationen durch, die zeigten, dass die Methode in der Praxis genauso gut funktioniert wie die Zufallsmethoden, ohne Genauigkeitsverlust.
Was noch offen ist: Sie geben zu, dass sie zwar glauben, dass die Methode sogar besser ist, als ihr aktueller Beweis nahelegt (da sie weniger Speicher für große Listen benötigt), sie aber noch nicht vollständig die „Konzentrationsungleichheit“ bewiesen haben, die dies für jeden mögliche Input garantieren würde, sondern nur für den spezifischen Satz an Zentroiden, die sie schützen.

Warum das wichtig ist

Dies ist nicht nur ein mathematisches Rätsel; es ist ein Schlüssel, um private KI praktikabel zu machen. Derzeit, wenn Sie beispielsweise einen privaten medizinischen Fall an einen Spezialisten routen oder eine Zahlung verifizieren möchten, ohne die Details preiszugeben, dauert der „Beweis“ Minuten und Gigabytes an Daten. Mit dieser neuen deterministischen Projektion schlagen die Autoren vor, dass wir diese Zeit auf Sekunden und die Datengröße auf Kilobytes reduzieren könnten, während die Privatsphäre-Garantien absolut solide bleiben.

Sie haben nicht nur eine neue Zahl gefunden; sie haben einen Weg gefunden, die „Magie“ von Zero-Knowledge-Proofs auf einer festen, öffentlichen Spur laufen zu lassen, die jeder verifizieren kann, wodurch die Notwendigkeit teurer, zufälliger „Würfelwürfe“ entfällt, die alles verlangsamen. Es ist ein Schritt in Richtung einer Zukunft, in der Ihre digitale Privatsphäre nicht auf Kosten Ihrer Geduld geht.

Technische Zusammenfassung: Deterministische Johnson–Lindenstrauss-Projektionen aus Pisot- $\beta$ -Transformationen für das Zero-Knowledge Private Routing

1. Problemstellung

In Zero-Knowledge (ZK)-Beweissystemen für das Private Routing muss ein Prover zertifizieren, dass eine Nachrichten-Einbettung $v \in \mathbb{R}^d$ zu einer erlaubten semantischen Klasse gehört, die durch eine Menge öffentlicher Zentroiden $C = \{c_1, \dots, c_N\}$ definiert ist. Dies erfolgt typischerweise über einen Nearest-Centroid-Test, der $O(Nd)$ arithmetische Constraints erfordert. Angesichts moderner Einbettungsdimensionen ( $d \in [768, 4096]$ ) dominiert diese Anzahl an Constraints die Beweisgröße und die Prover-Zeit.

Die Standardlösung ist eine Johnson–Lindenstrauss (JL)-Projektion, um die Dimension auf $m \ll d$ zu reduzieren. Klassische JL-Matrizen sind jedoch zufällig. In einem ZK-Kontext erzwingt die Verwendung einer Zufallsmatrix den Circuit dazu, die Matrix zu committen und deren korrekte Stichprobenziehung zu beweisen, was genau die Rechenkosten reintroduziert, die die Projektion eigentlich eliminieren sollte. Zudem erfordern Zufallsmatrizen den Beweis des Sampling-Prozesses, was ein Leakage-Risiko schafft. Die Herausforderung besteht darin, eine öffentliche, deterministische und feste Projektionsmatrix zu konstruieren, die:

Distanzen nachweislich bewahrt.
Native zu dem endlichen Körper des Circuits ist.
Keine In-Circuit-Zufälligkeit oder Sampling-Beweise erfordert.

2. Methodik

Die Autoren schlagen vor, die Projektionsmatrix $A$ aus der standardisierten Orbit eines Pisot- $\beta$ -Transformation zu konstruieren.

Die Abbildung: Eine $\beta$ -Transformation $T_\beta x = \beta x - \lfloor \beta x \rfloor$ auf dem Einheitsintervall, wobei $\beta > 1$ eine Pisot-Zahl ist (eine algebraische ganze Zahl, deren Galois-Konjugierte strikt innerhalb des Einheitskreises liegen, z. B. das Goldene Verhältnis).
Dynamik: Die Abbildung ist ein deterministisches „Stretch-and-Fold“-chaotisches System mit einem eindeutigen invarianten Parry-Maß $\mu$ . Da $\beta$ eine Pisot-Zahl ist, besitzt der Transfer-Operator der Abbildung eine Spektrallücke (Spectral Gap), was dazu führt, dass Korrelationen zwischen Observablen geometrisch abfallen ( $|r_k| \le C\theta^k$ ).
Matrixkonstruktion:
- Ein öffentlicher Seed $x_0$ wird ausgewählt.
- Ein Sampling-Gap $g$ wird fixiert, um sicherzustellen, dass die Stichproben jenseits der Korrelationszeit entnommen werden.
- Die Einträge der Matrix $A_{ij}$ werden sequenziell mit den normalisierten Orbit-Werten $z_p = \psi(T_\beta^{pg} x_0)$ gefüllt.
- Die Projektion ist $\Phi(v) = Av/\sqrt{m}$ .
Reproduzierbarkeit im endlichen Körper: Im Gegensatz zu generischen chaotischen Maps ist die Pisot-Eigenschaft entscheidend dafür, dass der Orbit exakt in einem festen endlichen Körper reproduzierbar ist. Die Kosten für die Generierung von $k$ Schritten liegen linear in $k$ (speziell $O(k \log_2 \beta)$ Bits), während generische chaotische Maps (wie die Logistische Map) ein exponentielles Wachstum der benötigten Präzision ( $O(2^k)$ Bits) erfordern, um exakte Arithmetik beizubehalten.

3. Zentrale Beiträge

Das Paper präsentiert vier wesentliche theoretische und praktische Beiträge:

Dimensionsfreie Bias- und Varianzgrenzen:
- Bias: Die Autoren beweisen, dass der Bias des quadratischen Norm-Schätzers durch einen Term begrenzt ist, der geometrisch mit dem Sampling-Gap $g$ abfällt und unabhängig von der Umgebungssdimension $d$ ist (Lemma 1). Dies wird aus der Spektrallücke der $\beta$ -Map abgeleitet und bietet eine stärkere Garantie als Standard-Äquidistributions-Argumente.
- Varianz: Sie zeigen, dass die Varianz des Schätzers als $V_0/m$ skaliert. Entscheidend ist, dass unter einer erklärten Konzentrationshypothese die Konstante $V_0$ dimensionsfrei ist (wächst nicht mit $d^2$ ), anders als grobe Schranken, die $O(d^2)$ suggerieren. Dies impliziert, dass eine feste Projektionsdimension $m$ ausreicht, unabhängig davon, wie groß $d$ wird.
Existenz eines einzelnen öffentlichen Seeds:
- Theorem 1 beweist, dass ein einzelner öffentlicher Seed $x_0$ existiert, der alle $\binom{N}{2}$ paarweisen Zentroid-Distanzen innerhalb von $(1 \pm \varepsilon)$ bewahrt.
- Dieser Seed kann über eine effiziente Offline-Suche gefunden werden. Sobald dieser gefunden ist, ist die Matrix fix, öffentlich und erfordert keine Randomness-Commitment während des ZK-Beweises.
Exakte Reproduzierbarkeit via Pisot-Eigenschaft:
- Das Paper identifiziert, dass die Pisot-Eigenschaft (nicht nur generische Chaos) für den ZK-Einsatz essenziell ist. Sie garantiert, dass der Orbit exakt in einem festen endlichen Körper mit linearen Rechenkosten pro Schritt reproduziert werden kann. Generische chaotische Maps scheitern hier aufgrund des exponentiellen Wachstums der erforderlichen Präzision (Nenner), um Floating-Point-Divergenz zu vermeiden.
Robustheit und Suche:
- Ein zertifizierbarer Robustheitsradius in geschlossener Form wird bereitgestellt (Proposition 1), der definiert, welche maximale Perturbation eine Query verträgt, ohne ihren nächsten projizierten Zentroiden zu ändern.
- Die Suche nach dem Seed ist unkonditional (garantiert durch Varianzgrenzen), kann aber auf eine logarithmische Abhängigkeit von $N$ verbessert werden, falls eine spezifische Konzentrationsungleichung für die Spectral-Gap-Map gilt.

4. Experimentelle Ergebnisse

Die Konstruktion wurde gegen sechs Standard-Projektionen evaluiert: Gauß, Rademacher, Achlioptas Sparse, Subsampled Randomized Hadamard Transform (SRHT) und eine chaotische Sequenz-Matrix (Yu et al.).

Statistische Qualität: Die Pisot-Projektion erreicht die statistische Qualität von Zufallsprojektionen.
- Varianzrate: Die Varianz des Schätzers folgt dem $1/m$ -Gesetz und überschneidet sich mit der $2/m$ -Referenz von Gauß-JL.
- Dimensionsunabhängigkeit: Die Varianzkonstante $V_0$ bleibt nahe bei 2 flach, während $d$ von 64 auf 1024 steigt, was die dimensionsfreie theoretische Vorhersage bestätigt.
- Distortion: Die Worst-Case-relative Distortion über alle Zentroid-Paare folgt der Gauß-JL-Baseline.
Aufgabenleistung: In einer 24-Klassen-Nearest-Centroid-Routing-Aufgabe mit $d=256$ erreichte die Pisot-Projektion eine Genauigkeit von 100 % bei $m=32$ (eine 8-fache Kompression), identisch mit anderen Methoden.
Reproduzierbarkeit: Simulationen bestätigten, dass Floating-Point-Implementierungen nach $\approx 50-70$ Schritten von den exakten Orbits divergieren (entsprechend den Lyapunov-Vorhersagen), während die Pisot- $\beta$ -adische Repräsentation exakt und kompakt bleibt (139 Bits für 200 Schritte vs. $1.66 \times 10^6$ Bits für eine logistische Map).

5. Bedeutung und Ansprüche

Das Paper behauptet, dass diese Konstruktion die einzige Methode ist, die drei kritische Anforderungen für das ZK Private Routing gleichzeitig erfüllt:

Frei von In-Circuit-Randomness: Kein Bedarf, die Stichprobenziehung einer Zufallsmatrix zu committen oder zu beweisen.
Exakt reproduzierbar in einem festen endlichen Körper: Erreicht durch die Pisot-Eigenschaft bei einem pro-Schritt-Kostenfaktor von $\log_2 \beta$ , wodurch die $O(2^k)$ -Kosten generischer chaotischer Maps vermieden werden.
Statistisch äquivalent zu Zufallsprojektionen: Matcht die Varianzrate und die Distortion-Eigenschaften von Standard-JL-Matrizen.

Die Autoren merken an, dass während die statistische Qualität bewiesen ist, der theoretische Schritt, die unkonditionale $O(N^2)$ Seed-Suche auf eine konditionale $O(\log N)$ Bindung zu heben, auf einer spezifischen Konzentrationsungleichung für den Transfer-Operator beruht, was ein offener theoretischer Schritt bleibt. Praktisch ermöglicht die Methode den Wechsel von Minuten/Gigabytes an Beweiserzeugung zu Sekunden, was verifizierbares privates Routing für hochdimensionale Embeddings praktikabel macht.