⚡ electrical engineering

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

Cet article introduit une projection de Johnson–Lindenstrauss déterministe et compatible avec le savoir nul (zero-knowledge), dérivée des transformations de Pisot $\beta$ , qui élimine le besoin de l'aléatoire coûteux en circuit grâce à l'utilisation d'une graine publique unique pour obtenir une variance indépendante de la dimension et une reproductibilité exacte sur corps finis tout en préservant les distances par paires.

Auteurs originaux : I. Dey, I. Cherkaoui

Publié 2026-08-14

📖 7 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : I. Dey, I. Cherkaoui

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

Imaginez un monde où votre vie numérique est une série de poignées de main secrètes. Vous voulez prouver à un videur que vous appartenez à un club VIP sans montrer votre pièce d'identité, ou prouver à une banque que vous avez assez d'argent sans révéler votre solde. C'est la magie des « Preuves à connaissance nulle » (Zero-Knowledge Proofs ou ZK) : une façon de dire « Je connais le secret » sans jamais murmurer le secret lui-même. Mais voici le hic : pour prouver que vous appartenez au bon groupe, votre identité numérique est souvent un nuage massif et complexe de nombres (un vecteur de haute dimension). Vérifier si ce nuage correspond à la liste VIP, c'est comme essayer de trouver un grain de sable spécifique dans une montagne ; cela demande tellement de puissance et de temps de calcul que cela ralentit tout.

Pour corriger cela, les scientifiques utilisent une astuce appelée la projection « Johnson-Lindenstrauss » (JL). Considérez cela comme une photocopieuse magique qui écrase une sculpture géante en 3D pour en faire une ombre plate en 2D. Étonnamment, si vous l'écrasez de la bonne manière, les distances entre les points dans l'ombre restent exactement les mêmes que dans la sculpture originale. Cela rend la tâche du « videur » facile et rapide. Cependant, il y a un obstacle : la façon standard de construire cette machine à écraser implique de lancer un dé numérique. La machine est aléatoire, donc pour prouver que vous n'avez pas dévié du protocole, vous devez prouver que vous avez lancé le dé correctement. Cette preuve est si lourde qu'elle annule toute la vitesse gagnée en compressant les données. Nous avons besoin d'une machine à écraser qui soit fixe, publique et qui n'ait pas besoin de lancer un dé pour prouver qu'elle est équitable.

Ce document présente une nouvelle façon de construire cette machine en utilisant un type spécial de mathématiques appelé « transformations $\beta$ -Pisot ». Les auteurs, I. Dey et I. Cherkaoui, ont construit une projection déterministe (non aléatoire) qui fonctionne aussi bien que les projections aléatoires, mais qui est parfaitement reproductible par n'importe qui, n'importe où, sans avoir besoin de prouver une graine aléatoire.

Le Problème : Le goulot d'étranglement du « Aléatoire »

Dans le monde du routage privé — où un agent d'IA décide quel modèle expert doit traiter un message privé — le message est transformé en une longue liste de nombres. Pour préserver la confidentialité, l'agent prouve que le message appartient à une catégorie « sûre » en le comparant à une liste de « centroïdes » connus (des exemples moyens de messages sûrs). Cette comparaison est coûteuse.

La solution habituelle est de réduire la liste de nombres en utilisant une matrice aléatoire (la projection JL). Mais parce que la matrice est aléatoire, l'ordinateur doit s'y engager et prouver qu'elle a été générée équitablement. Cette preuve est si coûteuse qu'elle déjoue l'objectif même de la réduction des données. Les auteurs soutiennent que nous avons besoin d'une matrice qui soit publique, fixe et identique pour tout le monde, afin qu'aucune preuve de l'aléa ne soit nécessaire.

La Solution : La machine « Étirer-et-Replier »

Les auteurs proposent de construire cette matrice fixe en utilisant une carte chaotique appelée transformation $\beta$ -Pisot.

L'analogie : Imaginez un morceau de pâte à pain. Vous l'étirez (multiplication par un nombre $\beta$ ) puis vous le repliez sur lui-même (prise du reste). C'est un processus « chaotique » ; si vous commencez avec deux points de pâte presque identiques, ils finiront rapidement par se retrouver dans des endroits complètement différents. Ce chaos est généralement excellent pour brouiller les données, mais il est terrible pour les ordinateurs qui doivent s'accorder sur le résultat.
Le problème du chaos normal : Si deux ordinateurs tentent de simuler cet étirement et ce repliement, de minuscules différences dans leur calcul (comme des erreurs d'arrondi) les feront diverger rapidement. Un ordinateur pourrait penser que la pâte est à la position A, tandis qu'un autre pense qu'elle est à la position B. Ils ne peuvent pas s'accorder sur la matrice.
La magie de Pisot : Les auteurs utilisent un type spécial de nombre appelé nombre de Pisot (comme le nombre d'or, 1,618, ou le nombre plastique, 1,325). Ces nombres possèdent une propriété algébrique spéciale : même si le processus est chaotique, l'« orbite » (le chemin que prend la pâte) peut être calculée exactement à l'aide d'un ensemble fini de règles.
- Le résultat : Deux ordinateurs peuvent exécuter la même simulation d'« étirement et de repliement » et obtenir le même résultat exact, bit par bit, sans erreurs d'arrondi. C'est comme avoir une recette qui fonctionne parfaitement, que vous utilisiez une cuillère en bois ou une en métal, tant que vous suivez les étapes.

Ce qu'ils ont trouvé

L'équipe a prouvé que cette matrice déterministe fonctionne aussi bien que les matrices aléatoires, mais avec quelques avantages clés :

Elle préserve les distances : Ils ont prouvé mathématiquement que les données « écrasées » conservent les distances entre les points presque exactement comme les originales. L'erreur (le biais) est infime et ne s'aggrave pas même si les données deviennent énormes.
C'est rapide et peu coûteux : Comme la matrice est fixe et publique, l'ordinateur n'a pas besoin de passer du temps à prouver qu'elle a été générée équitablement. Il utilise simplement la recette convenue à l'avance.
C'est reproductible : Ils ont montré que, tandis qu'une carte chaotique générique (comme la célèbre « carte logistique ») nécessiterait une quantité de mémoire impossible à calculer exactement (croissance exponentielle), la carte Pisot ne nécessite qu'une quantité de mémoire infime et fixe (croissance linéaire).
- Le test : Dans leurs simulations, ils ont comparé leur méthode Pisot à six autres méthodes standards, incluant des matrices gaussiennes aléatoires et d'autres cartes chaotiques.
- Le résultat : La méthode Pisot a parfaitement égalé la qualité statistique des matrices aléatoires. Le « bruit » dans la mesure était le même, et la capacité à router les messages correctement était identique. En fait, ils ont découvert qu'une seule « graine » publique (le point de départ de la pâte) pouvait préserver les distances pour toutes les paires de centroïdes dans une grande liste.

Le revers de la médaille (et l'avenir)

Les auteurs sont très clairs sur ce qu'ils ont accompli et sur ce qu'ils n'ont pas encore fait.

Ce qui est prouvé : Ils ont mathématiquement prouvé que le biais est faible et que la variance (le bruit) se comporte bien. Ils ont prouvé qu'une bonne graine existe et peut être trouvée par recherche.
Ce qui est mesuré : Ils ont mené des simulations montrant que la méthode fonctionne aussi bien que les méthodes aléatoires en pratique, sans perte de précision.
Ce qui reste ouvert : Ils admettent que, bien qu'ils croient que la méthode est encore meilleure que ce que suggère leur preuve actuelle (nécessitant moins de mémoire pour de grandes listes), ils n'ont pas encore pleinement prouvé l'« inégalité de concentration » qui garantirait cela pour n'importe quelle entrée possible, seulement pour l'ensemble spécifique de centroïdes qu'ils protègent.

Pourquoi cela importe

Il ne s'agit pas seulement d'un puzzle mathématique ; c'est une clé pour rendre l'IA privée concrète. Actuellement, si vous voulez router un cas médical privé vers un spécialiste ou vérifier un paiement sans en révéler les détails, la « preuve » prend des minutes et des gigaoctets de données. Avec cette projection déterministe, les auteurs suggèrent que nous pourrions réduire ce temps à des secondes et la taille des données à des kilo-octets, tout en maintenant des garanties de confidentialité solides.

Ils n'ont pas seulement trouvé un nouveau nombre ; ils ont trouvé un moyen de faire fonctionner la « magie » des preuves à connaissance nulle sur une piste fixe et publique que n'importe qui peut vérifier, supprimant ainsi le besoin de coûteux « lancers de dés » aléatoires qui ralentissent tout le processus. C'est un pas vers un futur où votre confidentialité numérique ne se fera pas au détriment de votre patience.

Résumé Technique : Projections de Johnson–Lindenstrauss Déterministes à partir de Transformations $\beta$ -Pisot pour le Routage Privé en Preuve à Divulgation Nulle (Zero-Knowledge)

1. Énoncé du Problème

Dans les systèmes de preuve à divulgation nulle (ZK) pour le routage privé, un prouveur doit certifier qu'un plongement de message $v \in \mathbb{R}^d$ appartient à une classe sémantique autorisée définie par un ensemble de centroïdes publics $C = \{c_1, \dots, c_N\}$ . Cela se fait généralement via un test de plus proche centroïde, qui nécessite $O(Nd)$ contraintes arithmétiques. Étant donné les dimensions d'embedding modernes ( $d \in [768, 4096]$ ), ce nombre de contraintes domine la taille de la preuve et le temps de calcul du prouveur.

Le remède standard est une projection de Johnson–Lindenstrauss (JL) pour réduire la dimension à $m \ll d$ . Cependant, les matrices JL classiques sont aléatoires. Dans un contexte ZK, l'utilisation d'une matrice aléatoire force le circuit à s'engager sur la matrice et à prouver son échantillonnage correct, réintroduisant le coût computationnel même que la projection était censée éliminer. De plus, les matrices aléatoires nécessitent de prouver le processus d'échantillonnage, ce qui crée un risque de fuite. Le défi consiste à construire une matrice de projection publique, déterministe et fixe qui :

Préserve les distances par paires de manière prouvable.
Est native au corps fini du circuit.
Ne nécessite aucun aléa ou preuve d'échantillonnage dans le circuit.

2. Méthodologie

Les auteurs proposent de construire la matrice de projection $A$ à partir de l'orbite normalisée d'une transformation $\beta$ -Pisot.

La Carte : Une transformation $\beta$ $T_\beta x = \beta x - \lfloor \beta x \rfloor$ sur l'intervalle unité, où $\beta > 1$ est un nombre Pisot (un entier algébrique dont les conjugués de Galois se situent strictement à l'intérieur du disque unité, par exemple le nombre d'or).
Dynamique : La carte est un système chaotique déterministe d'« étirement et repliement » possédant une mesure de Parry invariante unique $\mu$ . Crucialement, parce que $\beta$ est un nombre Pisot, l'opérateur de transfert de la carte possède un fossé spectral (spectral gap), ce qui fait que les corrélations entre les observables décroissent géométriquement ( $|r_k| \le C\theta^k$ ).
Construction de la Matrice :
- Une graine publique $x_0$ est sélectionnée.
- Un intervalle d'échantillonnage $g$ est fixé pour garantir que les échantillons sont prélevés au-delà du temps de corrélation.
- Les entrées de la matrice $A_{ij}$ sont remplies séquentiellement avec les valeurs d'orbite normalisées $z_p = \psi(T_\beta^{pg} x_0)$ .
- La projection est $\Phi(v) = Av/\sqrt{m}$ .
Reproductibilité dans un Corps Fini : Contrairement aux cartes chaotiques génériques, la propriété Pisot garantit que l'orbite est exactement reproductible dans un corps fini fixe. Le coût de génération de $k$ étapes est linéaire en $k$ (spécifiquement $O(k \log_2 \beta)$ bits), alors que les cartes chaotiques génériques (comme la carte logistique) nécessitent une croissance exponentielle de la précision (dénominateurs) pour maintenir une arithmétique exacte.

3. Principales Contributions

Le papier présente quatre contributions théoriques et pratiques majeures :

Bornes de Biais et de Variance Indépendantes de la Dimension :
- Biais : Les auteurs prouvent que le biais de l'estimateur de la norme au carré est borné par un terme décroissant géométriquement avec l'intervalle d'échantillonnage $g$ , indépendamment de la dimension ambiante $d$ (Lemme 1). Ceci est dérivé du fossé spectral de la $\beta$ -map, offrant une garantie plus forte que les arguments d'équidistribution standards.
- Variance : Ils montrent que la variance de l'estimateur suit une loi de $V_0/m$ . Crucialement, sous une hypothèse de concentration énoncée, la constante $V_0$ est indépendante de la dimension (ne croît pas avec $d^2$ ), contrairement aux bornes grossières qui suggèrent $O(d^2)$ . Cela implique qu'une dimension de projection $m$ fixe suffit, quelle que soit la taille de $d$ .
Existence d'une Graine Publique Unique :
- Le Théorème 1 prouve qu'il existe une graine publique $x_0$ unique qui préserve toutes les $\binom{N}{2}$ distances de paires de centroïdes à $(1 \pm \varepsilon)$ .
- Cette graine peut être trouvée via une recherche hors ligne efficace. Une fois trouvée, la matrice est fixe, publique, et ne nécessite aucun engagement d'aléa lors de la preuve ZK.
Reproductibilité Exacte via la Propriété Pisot :
- Le papier identifie que la propriété Pisot (et non seulement le chaos générique) est essentielle pour le déploiement ZK. Elle garantit que l'orbite peut être reproduite exactement dans un corps fini fixe avec un coût par étape de $\log_2 \beta$ . Les cartes chaotiques génériques échouent ici en raison de la croissance exponentielle de la précision requise (dénominateurs) pour éviter la divergence en virgule flottante.
Robustesse et Recherche :
- Un rayon de robustesse certifiable en forme close est fourni (Proposition 1), définissant la perturbation maximale qu'une requête peut subir sans changer son centroïde projeté le plus proche.
- La recherche de la graine est inconditionnelle (garantie par les bornes de variance) mais peut être améliorée pour une dépendance logarithmique en $N$ si une inégalité de concentration spécifique pour la carte à fossé spectral est vérifiée.

4. Résultats Expérimentaux

La construction a été évaluée contre six projections standards : Gaussienne, Rademacher, Achlioptas sparse, Subsampled Randomized Hadamard Transform (SRHT), et une matrice de séquence chaotique (Yu et al.).

Qualité Statistique : La projection Pisot correspond à la qualité statistique des projections aléatoires.
- Taux de Variance : La variance de l'estimateur suit la loi $1/m$ et chevauche la référence $2/m$ de la JL Gaussienne.
- Indépendance de la Dimension : La constante de variance $V_0$ reste stable autour de 2 lorsque $d$ passe de 64 à 1024, confirmant la prédiction théorique d'indépendance de la dimension.
- Distorsion : La distorsion relative maximale sur toutes les paires de centroïdes suit la ligne de base de la JL Gaussienne.
Performance de la Tâche : Dans une tâche de routage par plus proche centroïde à 24 classes avec $d=256$ , la projection Pisot a récupéré 100 % de précision à $m=32$ (une compression de 8x), identique aux autres méthodes.
Reproductibilité : Les simulations ont confirmé que les implémentations en virgule flottante divergent des orbites exactes après $\approx 50-70$ étapes (correspondant aux prédictions de Lyapunov), tandis que la représentation $\beta$ -adique de Pisot reste exacte et compacte (139 bits pour 200 étapes contre $1,66 \times 10^6$ bits pour une carte logistique).

5. Signification et Revendications

Le papier affirme que cette construction est la seule méthode qui satisfait simultanément trois exigences critiques pour le routage privé ZK :

Exempte d'aléa dans le circuit : Pas besoin de s'engager sur ou de prouver l'échantillonnage d'une matrice aléatoire.
Exactement reproductible dans un corps fini fixe : Grâce à la propriété Pisot, évitant le coût $O(2^k)$ des cartes chaotiques génériques.
Statistiquement équivalente aux projections aléatoires : Correspond au taux de variance et aux propriétés de distorsion des matrices JL standards.

Les auteurs notent que bien que la qualité statistique soit prouvée, l'étape théorique consistant à passer de la recherche de graine $O(N^2)$ inconditionnelle à une borne $O(\log N)$ conditionnelle repose sur une inégalité de concentration spécifique pour l'opérateur de transfert, ce qui reste une étape théorique ouverte. Pratiquement, la méthode permet de passer de minutes/gigaoctets de génération de preuve à quelques secondes, rendant le routage privé vérifiable réalisable pour des embeddings de haute dimension.