⚡ electrical engineering

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

Questo articolo introduce una proiezione di Johnson–Lindenstrauss deterministica e compatibile con lo zero-knowledge, derivata dalle trasformazioni di Pisot $\beta$ , che elimina la necessità di costosa casualità in circuito utilizzando un singolo seme pubblico per ottenere una varianza indipendente dalla dimensione e una riproducibilità esatta in campo finito, preservando al contempo le distanze a coppie.

Autori originali: I. Dey, I. Cherkaoui

Pubblicato 2026-08-14

📖 7 min di lettura🧠 Approfondimento

CC BY 4.0

Autori originali: I. Dey, I. Cherkaoui

Articolo originale sotto licenza CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Questa è una spiegazione generata dall'IA dell'articolo qui sotto. Non è stata scritta né approvata dagli autori. Per precisione tecnica, consulta l'articolo originale. Leggi il disclaimer completo

Immaginate un mondo in cui la vostra vita digitale è una serie di stretti di mano segreti. Volete dimostrare a un buttafuori che appartenete a un club VIP senza mostrare il vostro documento, o dimostrare a una banca che avete abbastanza soldi senza rivelare il vostro saldo. Questa è la magia delle "Zero-Knowledge Proofs" (ZK - Prove a Conoscenza Zero): un modo per dire "conosco il segreto" senza mai sussurrare il segreto stesso. Ma ecco il problema: per dimostrare di appartenere al gruppo giusto, la vostra identità digitale è spesso una nuvola enorme e complessa di numeri (un vettore ad alta dimensionalità). Controllare se questa nuvola corrisponde alla lista dei VIP è come cercare un granello di sabbia specifico in una montagna; richiede così tanta potenza di calcolo e tempo da rallentare tutto.

Per risolvere questo problema, gli scienziati usano un trucco chiamato proiezione "Johnson-Lindenstrauss" (JL). Pensatela come a una fotocopiatrice magica che schiaccia una gigantesca scultura 3D in un'ombra piatta 2D. Sorprendentemente, se la schiacciate nel modo giusto, le distanze tra i punti nell'ombra rimangono esattamente le stesse che c'erano nella scultura originale. Questo rende il lavoro del "buttafuori" facile e veloce. Tuttavia, c'è un intoppo: il modo standard per costruire questa macchina che schiaccia prevede il lancio di un dado digitale. La macchina è casuale, quindi per dimostrare di non aver deviato dal protocollo, dovete dimostrare di aver lanciato il dado correttamente. Questa prova è così pesante che annulla tutta la velocità guadagnata schiacciando i dati. Abbiamo bisogno di una macchina per schiacciare che sia fissa, pubblica e che non richieda il lancio di un dado per essere considerata equa.

Questo articolo introduce un nuovo modo per costruire quella macchina usando un tipo speciale di matematica chiamata " $\beta$ -trasformazioni di Pisot". Gli autori, I. Dey e I. Cherkaoui, hanno costruito una proiezione deterministica (non casuale) che funziona altrettanto bene delle altre casuali, ma è perfettamente riproducibile da chiunque, ovunque, senza dover dimostrare un seme di casualità.

Il Problema: Il Collo di Bottiglia della "Casualità"

Nel mondo del routing privato — dove un agente IA decide quale modello esperto debba gestire un messaggio privato — il messaggio viene trasformato in una lunga lista di numeri. Per mantenere la privacy, l'agente dimostra che il messaggio appartiene a una categoria "sicura" confrontandolo con una lista di "centroidi" noti (esempi medi di messaggi sicuri). Questo confronto è costoso.

La soluzione abituale è rimpicciolire la lista di numeri usando una matrice casuale (la proiezione JL). Ma poiché la matrice è casuale, il computer deve impegnarsi su di essa e dimostrare che sia stata generata equamente. Questa prova è così onerosa che vanifica lo scopo stesso di rimpicciolire i dati. Gli autori sostengono che abbiamo bisogno di una matrice che sia pubblica, fissa e identica per tutti, in modo che non sia necessaria alcuna prova di casualità.

La Soluzione: La Macchina "Stira-e-Piega"

Gli autori propongono di costruire questa matrice fissa usando una mappa caotica chiamata $\beta$ -trasformazione di Pisot.

L'Analogia: Immaginate un pezzo di pasta. Lo stiriate (moltiplicandolo per un numero $\beta$ ) e poi lo ripiegate su se stesso (prendendo il resto). Questo è un processo "caotico"; se partite con due punti di pasta quasi identici, questi finiranno rapidamente in posizioni completamente diverse. Questo caos è solitamente ottimo per rimescolare i dati, ma è terribile per i computer che devono concordare sul risultato.
Il Problema con il Caos Normale: Se due computer provassero a simulare questo processo di stiramento e piegatura, piccole differenze nella loro matematica (come gli errori di arrotondamento) farebbero divergere rapidamente i risultati. Un computer potrebbe pensare che la pasta si trovi nella posizione A, mentre l'altro potrebbe pensare che sia nella posizione B. Non possono concordare sulla matrice.
La Magia di Pisot: Gli autori utilizzano un tipo speciale di numero chiamato numero di Pisot (come il Rapporto Aureo, 1.618, o il Numero Plastico, 1.325). Questi numeri hanno una proprietà algebrica speciale: anche se il processo è caotico, l'"orbita" (il percorso che la pasta compie) può essere calcolata esattamente usando un insieme finito di regole.
- Il Risultato: Due computer possono eseguire la stessa simulazione "stira-e-piega" e ottenere lo stesso identico risultato, bit per bit, senza errori di arrotondamento. È come avere una ricetta che funziona perfettamente sia che si usi un cucchiaio di legno che uno di metallo, purché si seguano i passaggi.

Cosa hanno scoperto

Il team ha dimostrato che questa matrice deterministica funziona altrettanto bene delle altre casuali, ma con alcuni vantaggi chiave:

Preserva le Distanze: Hanno dimostrato matematicamente che i dati "schiacciati" mantengono le distanze tra i punti quasi esattamente uguali a quelle originali. L'errore (bias) è minuscolo e non peggiora anche se i dati diventano enormi.
È Veloce ed Economica: Poiché la matrice è fissa e pubblica, il computer non deve spendere tempo a dimostrare che sia stata generata equamente. Utilizza semplicemente la ricetta concordata in precedenza.
È Riproducibile: Hanno dimostrato che, mentre una mappa caotica generica (come la famosa "mappa logistica") richiederebbe una quantità di memoria impossibile da calcolare esattamente (crescendo esponenzialmente), la mappa di Pisot richiede solo una quantità minima e fissa di memoria (crescendo linearmente).
- Il Test: Nelle loro simulazioni, hanno confrontato il metodo Pisot con altri sei metodi standard, incluse le matrici gaussiane casuali e altre mappe caotiche.
- L'Esito: Il metodo Pisot ha eguagliato perfettamente la qualità statistica delle matrici casuali. Il "rumore" nella misurazione era lo stesso e la capacità di instradare correttamente i messaggi era identica. In effetti, hanno scoperto che un singolo "seme" pubblico (il punto di partenza della pasta) poteva preservare le distanze per tutte le coppie di centroidi in una grande lista.

Il Limite (e il Futuro)

Gli autori sono molto chiari su ciò che hanno fatto e su ciò che non hanno fatto.

Ciò che è Provato: Hanno dimostrato matematicamente che il bias è piccolo e che la varianza (rumore) si comporta bene. Hanno dimostrato che esiste un buon seme e che può essere trovato tramite ricerca.
Ciò che è Misurato: Hanno eseguito simulazioni che mostrano come il metodo funzioni bene quanto quelli casuali nella pratica, senza perdita di accuratezza.
Ciò che è Ancora Aperto: Ammettono che, sebbene ritengano che il metodo sia persino migliore di quanto suggerisca la loro attuale prova (richiedendo meno memoria per liste grandi), non hanno ancora dimostrato completamente la "disuguaglianza di concentrazione" che garantirebbe questo per qualsiasi possibile input, ma solo per il set specifico di centroidi che stanno proteggendo.

Perché questo è importante

Questa non è solo un rompicapo matematico; è una chiave per rendere pratica l'IA privata. Attualmente, se volete instradare un caso medico privato a uno specialista o verificare un pagamento senza rivelarne i dettagli, la "prova" richiede minuti e gigabyte di dati. Con questa nuova proiezione deterministica, gli autori suggeriscono che potremmo ridurre quel tempo a secondi e la dimensione dei dati a chilobyte, mantenendo al contempo le garanzie di privacy incrollabili.

Non hanno solo trovato un nuovo numero; hanno trovato un modo per far sì che la "magia" delle prove a conoscenza zero giri su un binario fisso e pubblico che chiunque può verificare, eliminando la necessità di costosi e casuali "lanci di dadi" che rallentano tutto. È un passo verso un futuro in cui la vostra privacy digitale non debba andare a discapito della vostra pazienza.

Sintesi Tecnica: Proiezioni di Johnson–Lindenstrauss Deterministiche da Trasformazioni $\beta$ -Pisot per il Routing Privato in Zero-Knowledge

1. Definizione del Problema

Nei sistemi di prova a conoscenza zero (Zero-Knowledge, ZK) per il routing privato, un prover deve certificare che un embedding di un messaggio $v \in \mathbb{R}^d$ appartenga a una classe semantica consentita definita da un insieme di centroidi pubblici $C = \{c_1, \dots, c_N\}$ . Ciò avviene tipicamente tramite un test del centro più vicino, che richiede $O(Nd)$ vincoli aritmetici. Data la dimensione degli embedding moderni ( $d \in [768, 4096]$ ), questo conteggio di vincoli domina la dimensione della prova e il tempo del prover.

Il rimedio standard è una proiezione di Johnson–Lindenstrauss (JL) per ridurre la dimensione a $m \ll d$ . Tuttavia, le matrici JL classiche sono casuali. In un contesto ZK, l'uso di una matrice casuale costringe il circuito a impegnarsi (commit) sulla matrice e a dimostrare la sua corretta campionatura, reintroducendo proprio il costo computazionale che la proiezione mirava a eliminare. Inoltre, le matrici casuali richiedono la dimostrazione del processo di campionamento, creando un rischio di fuga di informazioni (leakage). La sfida consiste nel costruire una matrice di proiezione pubblica, deterministica e fissa che:

Preservi le distanze a coppia in modo dimostrabile.
Sia nativa al campo finito del circuito.
Non richieda casualità in-circuit o dimostrazioni di campionamento.

2. Metodologia

Gli autori propongono di costruire la matrice di proiezione $A$ partendo dall'orbita standardizzata di una trasformazione $\beta$ -Pisot.

La Mappa: Una $\beta$ -trasformazione $T_\beta x = \beta x - \lfloor \beta x \rfloor$ sull'intervallo unitario, dove $\beta > 1$ è un numero Pisot (un intero algebrico i cui coniugati di Galois giacciono strettamente all'interno del disco unitario, ad esempio, il rapporto aureo).
Dinamica: La mappa è un sistema caotico deterministico di tipo "stretch-and-fold" con una misura di Parry invariante unica $\mu$ . Fondamentalmente, poiché $\beta$ è un numero Pisot, l'operatore di trasferimento della mappa possiede un gap spettrale, causando un decadimento geometrico delle correlazioni tra gli osservabili ( $|r_k| \le C\theta^k$ ).
Costruzione della Matrice:
- Viene selezionato un seed pubblico $x_0$ .
- Un gap di campionamento $g$ è fissato per garantire che i campioni siano prelevati oltre il tempo di correlazione.
- Le voci della matrice $A_{ij}$ vengono riempite sequenzialmente con i valori dell'orbita normalizzati $z_p = \psi(T_\beta^{pg} x_0)$ .
- La proiezione è $\Phi(v) = Av/\sqrt{m}$ .
Riproducibilità in Campo Finito: A differenza delle mappe caotiche generiche, la proprietà Pisot garantisce che l'orbita sia esattamente riproducibile in un campo finito fisso. Il costo di generazione di $k$ passi è lineare in $k$ (specificamente $O(k \log_2 \beta)$ bit), mentre le mappe caotiche generiche (come la mappa logistica) richiedono una crescita esponenziale dei bit ( $O(2^k)$ ) per mantenere un'aritmetica esatta.

3. Contributi Principali

Il documento presenta quattro contributi teorici e pratici principali:

Limiti di Bias e Varianza Indipendenti dalla Dimensione:
- Bias: Gli autori dimostrano che il bias dello stimatore della norma al quadrato è limitato da un termine che decade geometricamente con il gap di campionamento $g$ , indipendentemente dalla dimensione ambiente $d$ (Lemma 1). Ciò deriva dal gap spettrale della $\beta$ -mappa, offrendo una garanzia più forte rispetto ai comuni argomenti di equidistribuzione.
- Varianza: Dimostrano che la varianza dello stimatore scala come $V_0/m$ . Fondamentalmente, sotto un'ipotesi di concentrazione dichiarata, la costante $V_0$ è indipendente dalla dimensione (non cresce con $d^2$ ), diversamente dai limiti grossolani che suggeriscono $O(d^2)$ . Ciò implica che una dimensione di proiezione $m$ fissa sia sufficiente indipendentemente da quanto grande diventi $d$ .
Esistenza di un Singolo Seed Pubblico:
- Il Teorema 1 dimostra che esiste un singolo seed pubblico $x_0$ che preserva tutte le $\binom{N}{2}$ distanze a coppia dei centroidi entro $(1 \pm \varepsilon)$ .
- Questo seed può essere trovato tramite una ricerca offline efficiente. Una volta trovato, la matrice è fissa, pubblica e non richiede impegni sulla casualità durante la prova ZK.
Riproducibilità Esatta tramite la Proprietà Pisot:
- Il documento identifica che la proprietà Pisot (non solo il caos generico) è essenziale per l'implementazione ZK. Essa garantisce che l'orbita possa essere riprodotta esattamente in un campo finito fisso con un costo computazionale lineare per passo. Le mappe caotiche generiche falliscono qui a causa della crescita esponenziale della precisione richiesta (denominatori) per evitare la divergenza del punto mobile.
Robustezza e Ricerca:
- Viene fornito un raggio di robustezza certificabile in forma chiusa (Proposizione 1), che definisce la massima perturbazione che una query può sostenere senza cambiare il suo centro più vicino proiettato.
- La ricerca del seed è incondizionata (garantita dai limiti di varianza) ma può essere migliorata a una dipendenza logaritmica da $N$ se una specifica disuguaglianza di concentrazione per la mappa del gap spettrale è valida.

4. Risultati Sperimentali

La costruzione è stata valutata contro sei proiezioni standard: Gaussiana, Rademacher, Achlioptas sparse, Subsampled Randomized Hadamard Transform (SRHT) e una matrice a sequenza caotica (Yu et al.).

Qualità Statistica: La proiezione Pisot eguaglia la qualità statistica delle proiezioni casuali.
- Tasso di Varianza: La varianza dello stimatore segue la legge $1/m$ e si sovrappone al riferimento $2/m$ di la proiezione JL Gaussiana.
- Indipendenza dalla Dimensione: La costante di varianza $V_0$ rimane piatta vicino a 2 mentre $d$ aumenta da 64 a 1024, confermando la previsione teorica di indipendenza dalla dimensione.
- Distorsione: La distorsione relativa massima su tutte le coppie di centroidi segue la linea di base della JL Gaussiana.
Performance del Task: In un compito di routing a centro più vicino con 24 classi e $d=256$ , la proiezione Pisot ha recuperato il 100% dell'accuratezza con $m=32$ (una compressione di 8x), identica agli altri metodi.
Riproducibilità: Le simulazioni hanno confermato che le implementazioni in virgola mobile divergono dalle orbite esatte dopo circa 50-70 passi (in linea con le previsioni di Lyapunov), mentre la rappresentazione $\beta$ -adica di Pisot rimane esatta e compatta (139 bit per 200 passi contro $1.66 \times 10^6$ bit per una mappa logistica).

5. Significato e Rivendicazioni

Il documento sostiene che questa costruzione è l'unico metodo che soddisfa simultaneamente tre requisiti critici per il routing privato ZK:

Privo di casualità in-circuit: Nessuna necessità di impegnarsi o dimostrare la campionatura di una matrice casuale.
Esattamente riproducibile in un campo finito fisso: Grazie alla proprietà Pisot, evitando il costo $O(2^k)$ delle mappe caotiche generiche.
Statisticamente equivalente alle proiezioni casuali: Eguaglia il tasso di varianza e le proprietà di distorsione delle matrici JL standard.

Gli autori osservano che, sebbene la qualità statistica sia dimostrata, il passaggio teorico per elevare il limite di ricerca del seed da incondizionato $O(N^2)$ a $O(\log N)$ dipende da una specifica disuguaglianza di concentrazione per l'operatore di trasferimento, che rimane un passaggio teorico aperto. In pratica, il metodo permette di passare da minuti/gigabyte di generazione della prova a pochi secondi, rendendo il routing privato verificabile per embedding ad alta dimensionalità.