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

Resumen Técnico: Proyecciones de Johnson–Lindenstrauss Deterministas a partir de Transformaciones Pisot $\beta$ para el Enrutamiento Privado de Conocimiento Cero

1. Planteamiento del Problema

En los sistemas de prueba de Conocimiento Cero (ZK) para el enrutamiento privado, un probador debe certificar que una incrustación de mensaje $v \in \mathbb{R}^d$ pertenece a una clase semántica permitida definida por un conjunto de centroides públicos $C = \{c_1, \dots, c_N\}$. Esto se realiza típicamente mediante una prueba de centroide más cercano, la cual requiere $O(Nd)$ restricciones aritméticas. Dado que las dimensiones de las incrustaciones modernas son elevadas ($d \in [768, 4096]$), este recuento de restricciones domina el tamaño de la prueba y el tiempo del probador.

El remedio estándar es una proyección de Johnson–Lindenstrauss (JL) para reducir la dimensión a $m \ll d$. Sin embargo, las matrices JL clásicas son aleatorias. En un contexto de ZK, el uso de una matriz aleatoria obliga al circuito a comprometerse con la matriz y probar su muestreo correcto, reintroduciendo precisamente el costo computacional que la proyección pretendía eliminar. Además, las matrices aleatorias requieren probar el proceso de muestreo, lo que crea un riesgo de filtración. El desafío es construir una matriz de proyección pública, determinista y fija que:

1. Preserve las distancias por pares de forma demostrable.
2. Sea nativa al campo finito del circuito.
3. No requiera aleatoriedad ni pruebas de muestreo dentro del circuito.

2. Metodología

Los autores proponen construir la matriz de proyección $A$ a partir de la órbita estandarizada de una transformación $\beta$ de Pisot.

• El Mapa: Una transformación $\beta$ $T_\beta x = \beta x - \lfloor \beta x \rfloor$ en el intervalo unitario, donde $\beta > 1$ es un número de Pisot (un entero algebraico cuyos conjugados de Galois se encuentran estrictamente dentro del disco unitario, por ejemplo, el número áureo).
• Dinámica: El mapa es un sistema caótico determinista de "estiramiento y plegado" con una medida de Parry $\mu$ invariante única. Crucialmente, debido a que $\beta$ es un número de Pisot, el operador de transferencia del mapa posee un brecha espectral (spectral gap), lo que causa que las correlaciones entre observables decaigan geométricamente ($|r_k| \le C\theta^k$).
• Construcción de la Matriz:
  • Se selecciona una semilla pública $x_0$.
  • Se fija un intervalo de muestreo $g$ para asegurar que las muestras se tomen más allá del tiempo de correlación.
  • Las entradas de la matriz $A_{ij}$ se completan secuencialmente con los valores de la órbita normalizados $z_p = \psi(T_\beta^{pg} x_0)$.
  • La proyección es $\Phi(v) = Av/\sqrt{m}$.
• Reproducibilidad en Campo Finito: A diferencia de los mapas caóticos genéricos, la propiedad de Pisot asegura que la órbita sea exactamente reproducible en un campo finito fijo. El costo de generar $k$ pasos es lineal en $k$ (específicamente $O(k \log_2 \beta)$ bits), mientras que los mapas caóticos genéricos (como el mapa logístico) requieren un crecimiento exponencial de bits ($O(2^k)$) para mantener una aritmética exacta.

3. Contribuciones Clave

El artículo presenta cuatro contribuciones teóricas y prácticas principales:

1. Límites de Sesgo y Varianza Independientes de la Dimensión:

   • Sesgo: Los autores demuestran que el sesgo del estimador de la norma al cuadrado está acotado por un término que decae geométricamente con el intervalo de muestreo $g$, independientemente de la dimensión ambiente $d$ (Lema 1). Esto se deriva de la brecha espectral del mapa $\beta$, ofreciendo una garantía más fuerte que los argumentos estándar de equidistribución.
   • Varianza: Demuestran que la varianza del estimador escala como $V_0/m$. Crucialmente, bajo una hipótesis de concentración establecida, la constante $V_0$ es independiente de la dimensión (no crece con $d^2$), a diferencia de los límites crudos que sugieren $O(d^2)$. Esto implica que una dimensión de proyección $m$ fija es suficiente sin importar cuán grande sea $d$.

2. Existencia de una Única Semilla Pública:

   • El Teorema 1 demuestra que existe una única semilla pública $x_0$ que preserva todas las $\binom{N}{2}$ distancias de centroides por pares dentro de $(1 \pm \varepsilon)$.
   • Esta semilla puede encontrarse mediante una búsqueda externa (offline) eficiente. Una vez encontrada, la matriz es fija, pública y no requiere compromiso de aleatoriedad durante la prueba ZK.

3. Reproducibilidad Exacta mediante la Propiedad de Pisot:

   • El artículo identifica que la propiedad de Pisot (no solo el caos genérico) es esencial para el despliegue en ZK. Garantiza que la órbita pueda reproducirse exactamente en un campo finito fijo con un costo computacional lineal por paso ($\log_2 \beta$), evitando el costo $O(2^k)$ de los mapas caóticos genéricos.

4. Robustez y Búsqueda:

   • Se proporciona un radio de robustez certificable de forma cerrada (Proposición 1), que define la perturbación máxima que una consulta puede soportar sin cambiar su centroide proyectado más cercano.
   • La búsqueda de la semilla es incondicional (garantizada por los límites de varianza) pero puede mejorar a una dependencia logarítmica de $N$ si se cumple una desigualdad de concentración específica para el mapa de brecha espectral.

4. Resultados Experimentales

La construcción fue evaluada contra seis proyecciones estándar: Gaussiana, Rademacher, Achlioptas dispersa, Transformada de Hadamard Aleatorizada Submuestreada (SRHT) y una matriz de secuencia caótica (Yu et al.).

• Calidad Estadística: La proyección de Pisot iguala la calidad estadística de las proyecciones aleatorias.
  • Tasa de Varianza: La varianza del estimador sigue la ley $1/m$ y se solapa con la referencia $2/m$ de la JL Gaussiana.
  • Independencia de la Dimensión: La constante de varianza $V_0$ permanece plana cerca de 2 a medida que $d$ aumenta de 64 a 1024, confirmando la predicción teórica de independencia de la dimensión.
  • Distorsión: La distorsión relativa máxima sobre todos los pares de centroides sigue la línea base de la JL Gaussiana.
• Desempeño de la Tarea: En una tarea de enrutamiento de centroide más cercano de 24 clases con $d=256$, la proyección de Pisot recuperó el 100% de la precisión con $m=32$ (una compresión de 8x), idéntica a otros métodos.
• Reproducibilidad: Las simulaciones confirmaron que las implementaciones de punto flotante divergen de las órbitas exactas después de $\approx 50-70$ pasos (coincidiendo con las predicencias de Lyapunov), mientras que la representación $\beta$-ádica de Pisot permanece exacta y compacta (139 bits para 200 pasos frente a $1.66 \times 10^6$ bits para un mapa logístico).

5. Significación y Reivindicaciones

El artículo afirma que esta construcción es el único método que satisface simultáneamente tres requisitos críticos para el enrutamiento privado en ZK:

1. Libre de aleatoriedad en el circuito: No hay necesidad de comprometerse con o probar el muestreo de una matriz aleatoria.
2. Exactamente reproducible en un campo finito fijo: Logrado mediante la propiedad de Pisot con un costo por paso de $\log_2 \beta$, evitando el costo $O(2^k)$ de los mapas caóticos genéricos.
3. Estadísticamente equivalente a las proyecciones aleatorias: Coincide con la tasa de varianza y las propiedades de distorsión de las matrices JL estándar.

Los autores señalan que, si bien la calidad estadística está probada, el paso teórico para elevar el límite de búsqueda de semilla incondicional $O(N^2)$ a un límite condicional $O(\log N)$ depende de una desigualdad de concentración específica para el operador de transferencia, lo cual sigue siendo un paso teórico abierto. Prácticamente, el método permite pasar de minutos/gigabytes de generación de pruebas a segundos, haciendo que el enrutamiento privado verificable sea factible para incrustaciones de alta dimensión.