⚡ electrical engineering

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

Dit artikel introduceert een deterministische, zero-knowledge-vriendelijke Johnson–Lindenstrauss-projectie afgeleid van Pisot $\beta$ -transformaties die de noodzaak voor kostbare in-circuit randomiteit elimineert door gebruik te maken van een enkele publieke seed om dimensievrije variantie en exacte eindig veld reproduceerbaarheid te bereiken, terwijl paarsgewijze afstanden behouden blijven.

Oorspronkelijke auteurs: I. Dey, I. Cherkaoui

Gepubliceerd 2026-08-14

📖 7 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: I. Dey, I. Cherkaoui

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Stel je een wereld voor waarin je digitale leven een reeks geheime handdrukken is. Je wilt aan een uitsmijter bewijzen dat je bij een VIP-club hoort zonder je ID te laten zien, of aan een bank bewijzen dat je genoeg geld hebt zonder je saldo te onthullen. Dit is de magie van "Zero-Knowledge Proofs" (ZK): een manier om te zeggen "Ik ken het geheim" zonder het geheim zelf ooit te fluisteren. Maar hier zit de crux: om te bewijzen dat je bij de juiste groep hoort, is je digitale identiteit vaak een enorme, complexe wolk van getallen (een hoogdimensionale vector). Controleren of deze wolk overeenkomt met de VIP-lijst is als het proberen te vinden van een specifiek zandkorreltje in een berg; het kost zoveel computerkracht en tijd dat het alles vertraagt.

Om dit op te lossen, gebruiken wetenschappers een truc genaamd de "Johnson-Lindenstrauss" (JL) projectie. Beschouw dit als een magische fotokopieermachine die een gigantisch 3D-beeldhouwwerk platdrukt tot een 2D-schaduw. Wonderbaarlijk genoeg, als je het precies goed platdrukt, blijven de afstanden tussen de punten in de schaduw exact hetzelfde als ze waren in het oorspronkelijke beeldhouwwerk. Dit maakt de taak van de "uitsmijter" gemakkelijk en snel. Er is echter een probleem: de standaardmanier om die platdrukkende machine te maken, involves het gooien van een digitale dobbelsteen. De machine is willekeurig, dus om te bewijzen dat je de dobbelsteen correct hebt gegooid, moet je bewijzen dat je de dobbelsteen correct hebt gegooid. Dit bewijs is zo zwaar dat het alle snelheid die je door het platdrukken van de data hebt gewonnen, tenietdoet. We hebben een platdrukkende machine nodig die vaststaat, publiek is en geen dobbelsteenworp nodig heeft om eerlijkheid te bewijzen.

Dit artikel introduceert een nieuwe manier om die machine te bouwen met behulp van een speciaal soort wiskunde die "Pisot $\beta$ -transformaties" wordt genoemd. De auteurs, I. Dey en I. Cherkaoui, hebben een deterministische (niet-willekeurige) projectie geconstrueerd die net zo goed werkt als de willekeurige varianten, maar die perfect reproduceerbaar is voor iedereen, overal, zonder dat er een bewijs van een willekeurige 'seed' nodig is.

Het Probleem: De "Willekeurige" Bottleneck

In de wereld van private routing—waar een AI-agent beslist welk expert-model een privèbericht moet afhandelen—wordt het bericht omgezet in een lange lijst met getallen. Om de privacy te waarborgen, bewijst de agent dat het bericht bij een "veilige" categorie hoort door het te vergelijken met een lijst van bekende "centroids" (gemiddelde voorbeelden van veilige berichten). Deze vergelijking is kostbaar.

De gebruikelijke oplossing is om de lijst met getallen te verkleinen met een willekeurige matrix (de JL-projectie). Maar omdat de matrix willekeurig is, moet de computer zich eraan committeren en bewijzen dat deze eerlijk is gegenereerd. Dit bewijs is zo kostbaar dat het het doel van het verkleinen van de data volledig tenietdoet. De auteurs stellen dat we een matrix nodig hebben die publiek, vast en identiek voor iedereen is, zodat er geen bewijs van willekeur nodig is.

De Oplossing: De "Rek-en-Vouw"-Machine

De auteurs stellen voor om deze vaste matrix te bouwen met behulp van een chaotische kaart genaamd een Pisot $\beta$ -transformatie.

De Analogie: Stel je een stuk deeg voor. Je rekt het uit (vermenigvuldigen met een getal $\beta$ ) en vouwt het vervolgens terug op zichzelf (neem de restwaarde). Dit is een "chaotisch" proces; als je begint met twee bijna identieke puntjes deeg, zullen ze snel op totaal verschillende plaatsen einden. Deze chaos is meestal geweldig voor het door elkaar husselen van data, maar is verschrikkelijk voor computers die het over de resultaten eens moeten worden.
Het Probleem met Normale Chaos: Als twee computers deze rek-en-vouw-simulatie proberen uit te voeren, zullen minuscule verschillen in hun wiskunde (zoals afrondingsfouten) ervoor zorgen dat ze snel uiteenlopen. De ene computer denkt misschien dat het deeg op positie A is, terwijl de andere denkt dat het op positie B is. Ze kunnen het niet eens worden over de matrix.
De Pisot-Magie: De auteurs gebruiken een speciaal type getal genaamd een Pisot-getal (zoals de Gulden Snede, 1.618, of het Plastic Getal, 1.325). Deze getallen hebben een speciale algebraïsche eigenschap: ook al is het proces chaotisch, de "orbit" (het pad dat het deeg aflegt) kan exact worden berekend met een eindige set regels.
- Het Resultaat: Twee computers kunnen exact dezelfde "rek-en-vouw"-simulatie draaien en krijgen het exacte resultieve resultaat, bit voor bit, zonder afrondingsfouten. Het is alsof je een recept hebt dat perfect werkt, of je nu een houten lepel of een metalen lepel gebruikt, zolang je de stappen maar volgt.

Wat Ze Hebben Gevonden

Het team heeft bewezen dat deze deterministische matrix net zo goed werkt als de wielekeurige, maar met een paar belangrijke voordelen:

Het Behoudt Afstanden: Ze hebben wiskundig bewezen dat de "samengeperste" data de afstanden tussen de punten bijna exact hetzelfde houdt als de originele. De fout (bias) is minuscuul en wordt niet groter, zelfs niet als de data enorm groot wordt.
Het Is Snel en Goedkoop: Omdat de matrix vast en publiek is, hoeft de computer geen tijd te besteden aan het bewijzen dat deze eerlijk is gegenereerd. De computer gebruikt gewoon het vooraf overeengekomen recept.
Het Is Reproduceerbaar: Ze hebben aangetoond dat terwijl een generieke chaotische kaart (zoals de beroemde "logistische kaart") een onmogelijke hoeveelheid geheugen zou vereisen om exact te berekenen (groeiend exponentieel), de Pisot-kaart slechts een kleine, vaste hoeveelheid geheugen vereist (groeiend lineair).
- De Test: In hun simulaties hebben ze hun Pisot-methode vergeleken met zes andere standaardmethoden, inclusclusief willekeurige Gaussische matrices en andere chaotische kaarten.
- De Uitkomst: De Pisot-methode kwam qua statistische kwaliteit perfect overeen met de willekeurige matrices. De "ruis" in de meting was hetzelfde, en het vermogen om berichten correct te routeren was identiek. Sterker nog, ze ontdekten dat een enkele publieke "seed" (het startpunt van het deeg) de afstanden voor alle paren centroids in een grote lijst kon behouden.

De Catch (en de Toekomst)

De auteurs zijn zeer duidelijk over wat ze wel en niet hebben gedaan.

Wat is Bewezen: Ze hebben wiskundig bewezen dat de bias klein is en dat de variantie (ruis) goed gedraagt. Ze hebben bewezen dat er een goede seed bestaat en dat deze gevonden kan worden door te zoeken.
Wat is Gemeten: Ze hebben simulaties uitgevoerd die laten zien dat de methode in de praktijk net zo goed werkt als de willekeurige methoden, zonder verlies van nauwkeurigheid.
Wat Nog Openstaat: Ze geven toe dat ze er weliswaar van overtuigd zijn dat de methode zelfs beter is dan hun huidige bewijs suggereert (het vereist minder geheugen voor grote lijsten), maar ze hebben de "concentratie-ongelijkheid" die dit zou garanderen voor elke mogelijke input nog niet volledig bewezen, alleen voor de specifieke set centroids die ze beschermen.

Waarom Dit Belangrijk Is

Dit is niet zomaar een wiskundige puzzel; het is een sleutel om private AI praktisch bruikbaar te maken. Momenteel, als je een private medische casus naar een specialist wilt routeren of een betaling wilt verifiëren zonder de details te onthullen, duurt het "bewijs" minuten en kost het gigabytes aan data. Met deze nieuwe deterministische projectie suggereren de auteurs dat we die tijd kunnen terugbrengen naar seconden en de datagrootte naar kilobytes, terwijl de privacygaranties rotsvast blijven.

Ze hebben niet alleen een nieuw getal gevonden; ze hebben een manier gevonden om de "magie" van zero-knowledge proofs op een vast, publiek spoor te laten lopen dat door iedereen geverifieerd kan worden, waardoor de noodzaak voor dure, willekeurige "dobbelsteenworpen" die alles vertragen, verdwijnt. Het is een stap naar een toekomst waar je digitale privacy niet ten koste gaat van je geduld.

Technische Samenvatting: Deterministische Johnson–Lindenstrauss Projecties vanuit Pisot $\beta$ -transformaties voor Zero-Knowledge Private Routing

1. Probleemstelling

In Zero-Knowledge (ZK) bewijs-systemen voor private routing moet een bewijzer certificeren dat een bericht-embedding $v \in \mathbb{R}^d$ behoort tot een toegestane semantische klasse, gedefinieerd door een set publieke zwaartepunten $C = \{c_1, \dots, c_N\}$ . Dit wordt doorgaans gedaan via een nearest-centroid test, die $O(Nd)$ rekenkundige constraints vereist. Gegeven moderne embedding-dimensies ( $d \in [768, 4096]$ ), domineert deze constraint-count de omvang van het bewijs en de tijd van de bewijzer.

De standaardoplossing is een Johnson–Lindenstrauss (JL) projectie om de dimensie te reduceren naar $m \ll d$ . Echter, klassieke JL-matrices zijn willekeurig. In een ZK-context dwingt het gebruik van een willekeurige matrix de circuit om de matrix te committen en de correcte sampling ervan te bewijzen, wat de computationele kosten die de projectie juist moest elimineren, opnieuw introduceert. Bovendien vereisen willekeurige matrices het bewijzen van het samplingproces, wat een risico op lekkage creëert. De uitdaging is om een publieke, deterministische en vaste projectiematrix te construeren die:

Afstanden tussen paren bewezen behoudt.
Natief is aan het eindige veld van het circuit.
Geen in-circuit willekeur of sampling-bewijzen vereist.

2. Methodologie

De auteurs stellen voor om de projectiematrix $A$ te construeren vanuit de gestandaardiseerde baan van een Pisot $\beta$ -transformatie.

De Afbeelding: Een $\beta$ -transformatie $T_\beta x = \beta x - \lfloor \beta x \rfloor$ op het eenheidsinterval, waarbij $\beta > 1$ een Pisot-getal is (een algebraïsche integer waarvan de Galois-conjugaten strikt binnen de eenheidsschijf liggen, bijvoorbeeld de gulden snede).
Dynamiek: De afbeelding is een deterministisch "stretch-and-fold" chaotisch systeem met een unieke invariante Parry-maat $\mu$ . Cruciaal is dat omdat $\beta$ een Pisot-getal is, de transferoperator van de afbeelding beschikt over een spectrale kloof (spectral gap), waardoor correlaties tussen observabelen geometrisch afnemen ( $|r_k| \le C\theta^k$ ).
Matrixconstructie:
- Een publieke seed $x_0$ wordt geselecteerd.
- Een sampling-gap $g$ wordt vastgesteld om ervoor te zorgen dat samples worden genomen voorbij de correlatietijd.
- De matrix-elementen $A_{ij}$ worden sequentieel ingevuld met de genormaliseerde baanwaarden $z_p = \psi(T_\beta^{pg} x_0)$ .
- De projectie is $\Phi(v) = Av/\sqrt{m}$ .
Reproduceerbaarheid in Eindige Velden: In tegenstelling tot generieke chaotische kaarten, zorgt de Pisot-eigenschap ervoor dat de baan exact reproduceerbaar is in een vast eindig veld. De kosten voor het genereren van $k$ stappen zijn lineair in $k$ (specifiek $O(k \log_2 \beta)$ bits), terwijl generieke chaotische kaarten (zoals de logistische kaart) een exponentiële groei van de benodigde precisie vereisen ( $O(2^k)$ bits) om exacte rekenkunde te handhaven.

3. Belangrijkste Bijdragen

Het artikel presenteert vier belangrijke theoretische en praktische bijdragen:

Dimensievrije Bias- en Variantie-bounds:
- Bias: De auteurs bewijzen dat de bias van de gekwadrateerde-norm schatter begrensd wordt door een term die geometrisch afneemt met de sampling-gap $g$ , onafhankelijk van de omgevingdimensie $d$ (Lemma 1). Dit is afgeleid van de spectrale kloof van de $\beta$ -afbeelding, wat een sterkere garantie biedt dan standaard equidistributie-argumenten.
- Variantie: Ze tonen aan dat de variantie van de schatter schaalt als $V_0/m$ . Cruciaal is dat onder een gestelde concentratiehypothese, de constante $V_0$ dimensievrij is (groeit niet met $d^2$ ), in tegen tegenstelling tot grove bounds die $O(d^2)$ suggereren. Dit impliceert dat een vaste projectiedimensie $m$ volstaat, ongeacht hoe groot $d$ wordt.
Bestaan van een Enkele Publieke Seed:
- Stelling 1 bewijst dat er een enkele publieke seed $x_0$ bestaat die alle $\binom{N}{2}$ paar-afstand tussen zwaartepunten binnen $(1 \pm \varepsilon)$ behoudt.
- Deze seed kan worden gevonden via een efficiënt offline zoekproces. Eenmaal gevonden, is de matrix vast, publiek en vereist deze geen willekeur-commitment tijdens het ZK-bewijs.
Exacte Reproduceerbaarheid via de Pisot-eigenschap:
- Het artikel identificeert dat de Pisot-eigenschap (en niet louter generieke chaos) essentieel is voor ZK-implementatie. Het garandeert dat de baan exact gereproduceerd kan worden in een vast eindig veld met een lineaire computationele kosten per stap. Generieke chaotische kaarten falen hier vanwege de exponentiële groei van de vereiste precisie (noemers) om divergentie in floating-point berekeningen te voorkomen.
Robuustheid en Zoektocht:
- Een gesloten vorm, certificeerbare robuustheidsradius wordt verstrekt (Propositie 1), die de maximale perturbatie definieert die een query kan verdragen zonder van zijn dichtstbijzijnde geprojecteerde zwaartepunt te veranderen.
- De zoektocht naar de seed is onvoorwaardelijk (gegarandeerd door variantie-bounds), maar kan worden verbeterd naar een logaritmische afhankelijkheid van $N$ indien een specifieke concentratie-ongelijkheid voor de spectrale-kloof-kaart standhoudt.

4. Experimentele Resultaten

De constructie werd geëvalueerd tegen zes standaardprojecties: Gaussische, Rademacher, Achlioptas sparse, Subsampled Randomized Hadamard Transform (SRHT), en een chaotische-sequentie matrix (Yu et al.).

Statistische Kwaliteit: De Pisot-projectie komt overeen met de statistische kwaliteit van willekeurige projecties.
- Variatie-snelheid: De variantie van de schatter volgt de $1/m$ -wet en overlapt met de $2/m$ referentie van de Gaussische JL.
- Dimensie-onafhankelijkheid: De variantie-constante $V_0$ blijft vlak nabij 2 terwijl $d$ toeneemt van 64 naar 1024, wat de dimensievrije theoretische voorspelling bevestigt.
- Distortie: De slechtst denkbare relatieve distortie over alle zwaartepunt-paren volgt de Gaussische JL-baseline.
Taakprestaties: In een 24-klasse nearest-centroid routing taak met $d=256$ , herstelde de Pisot-projectie 100% nauwkeurigheid bij $m=32$ (een 8x compressie), identiek aan andere methoden.
Reproduceerbaarheid: Simulaties bevestigden dat floating-point implementaties divergeren van exacte banen na $\approx 50-70$ stappen (overeenkomend met Lyapunov-voorspellingen), terwijl de Pisot $\beta$ -adische representatie exact en compact blijft (139 bits voor 200 stappen versus $1.66 \times 10^6$ bits voor een logistische kaart).

5. Betekenis en Claims

Het artikel claimt dat deze constructie de enige methode is die simultaan aan drie kritieke vereisten voor ZK private routing voldoet:

Vrij van in-circuit willekeur: Geen noodzaak om de sampling van een willekeurige matrix te committen of te bewijzen.
Exact reproduceerbaar in een vast eindig veld: Bereikt via de Pisot-eigenschap tegen een per-stap kost van $\log_2 \beta$ , waardoor de $O(2^k)$ kosten van generieke chaotische kaarten worden vermeden.
Statistisch equivalent aan willekeurige projecties: Komt overeen met de variantie-snelheid en distortie-eigenschappen van standaard JL-matrices.

De auteurs merken op dat hoewel de statistische kwaliteit bewezen is, de theoretische stap om de onvoorwaardelijke $O(N^2)$ seed-zoekbound te upgraden naar een conditionele $O(\log N)$ bound rust op een specifieke concentratie-ongelijkheid voor de transferoperator, wat een openstaand theoretisch punt blijft. In de praktijk maakt deze methode een verschuiving mogelijk van minuten/gigabytes aan bewijsgeneratie naar seconden, wat verifieerbare private routing voor hoog-dimensionale embeddings haalbaar maakt.