Exponentially Fewer-Server PIR from Sparser $S$-Decoding Polynomials

Resumen Técnico: Menos servidores exponencialmente para PIR mediante polinomios de decodificación $S$ más dispersos

Planteamiento del problema
La Recuperación de Información Privada (PIR, por sus siglas en inglés) permite a un usuario recuperar un elemento de una base de datos de tamaño $n$ mantenida por $s$ servidores no colusivos sin revelar el índice del elemento a ningún servidor individual. El objetivo principal es minimizar la complejidad de comunicación total. Mientras que los protocolos triviales requieren una comunicación de $O(n)$, trabajos previos establecieron que, para un número constante de servidores $s$, la comunicación podría reducirse a niveles subpolinomiales, específicamente $\exp(\tilde{O}(\sqrt{\log n}))$ para $s=3$ (Efremenko, 2009) y $\exp(\tilde{O}((\log n)^{1/s}))$ para un $s$ general bajo supuestosos de teoría de números específicos.

Sin embargo, persistía una brecha significativa en el compromiso entre el número de servidores $s$ y la complejidad de comunicación. Específicamente, dentro del marco de "vector de coincidencia + polinomio de decodificación $S$" (iniciado por Efremenko y refinado por Ghasemi, Kopparty y Sudan), las mejores construcciones conocidas requerían $s = 2^k$ o $s = 3k/2$ servidores para lograr una comunicación de $\exp(\tilde{O}((\log n)^{1/k}))$. Los límites inferiores teóricos de Ghasemi y Kopparty (2026) sugerían que la dispersión de los polinomios de decodificación necesarios podía ser tan baja como $k+1$, lo que implicaba la posibilidad de utilizar exponencialmente menos servidores para el mismo costo de comunicación. El problema abierto era si tales polinomios óptimamente dispersos podían construirse.

Metodología
Los autores abordan esto centrándose en la construcción de polinomios de decodificación $S$. Sea $m = p_1 \dots p_k$ un producto de $k$ primos distintos, y sea $S^*_m \subseteq \mathbb{Z}_m$ el conjunto canónico de residuos congruentes con 0 o 1 módulo cada $p_i$. Un polinomio de decodificación $S^*_m$-sobre un cuerpo finito $\mathbb{F}$ debe satisfacer $P(1)=1$ y $P(\gamma^j)=0$ para todo $j \in S^*_m \setminus \{0\}$, donde $\gamma$ es una raíz $m$-ésima primitiva de la unidad. La dispersión de $P$ (número de coeficientes no nulos) dicta directamente el número de servidores $s$ requeridos en el protocolo PIR.

La contribución técnica central del artículo es establecer una equivalencia entre la existencia de un polinomio de decodificación $S^*_m$ de dispersión $k+1$ y la existencia de una "rejilla de raíces de la unidad" (root-of-unity grid). Una rejilla de raíces de la unidad es una configuración de elementos $a_1, \dots, a_k \in \mathbb{F} \setminus \{0\}$ y elementos distintos $t_1, \dots, t_{k+1} \in \mathbb{F}$ tales que $1 + a_i t_j$ es una raíz $p_i$-ésima de la unidad para todo $i, j$.

Para construir estas rejillas, los autores proponen dos enfoques:

1. Método Probabilístico (Repunits Rugosos): Este es el enfoque principal utilizado para los resultados principales. Se basa en encontrar un primo $q$ e enteros $d_1, \dots, d_k$ tales que $q^{d_i}-1$ tenga un factor primo grande (específicamente, un número "rugoso" donde el mayor factor primo es al menos $(q^{d_i}-1)^{1-1/(3k)}$). La existencia de tales números está garantizada bajo un conjetura de teoría de números plausible.
2. Método Algebraico (Núcleos de Norma): Un enfoque secundario que utiliza la teoría de Galois y el mapa de norma para construir rejillas, el cual recupera con éxito el ejemplo original de Efremenko $m=7 \times 73$, pero no se generaliza tan ampliamente como el método probabilístico para los teoremas principales de los autores.

Para los regímenes donde el número de servidores $s$ crece con $n$ (superconstante), los autores emplean una técnica de "costura" (basada en Itoh y Suzuki, 2010) para combinar múltiples rejillas de raíces de la unidad sobre el mismo cuerpo en un único polinomio de decodificación.

Contribuciones Clave y Resultados

1. Resolución de la Brecha de Dispersión: Bajo una conjetura de teoría de números (Conjetura 1.1), los autores demuestran que para cualquier $k$ constante, existe un polinomio de decodificación $S^*_m$ de dispersión $k+1$ donde $m$ es un producto de $k$ primos distintos. Esto iguala el límite inferior establecido por Ghasemi y Kopparty, cerrando completamente la brecha exponencial entre los límites superiores e inferiores de la dispersión.

   • Conjetura 1.1: Para cada $k>1$, existe un primo $q \ge k+1$ e enteros distintos $d_i \ge 6$ tales que $q^{d_i}-1$ tiene un divisor primo $\ge (q^{d_i}-1)^{1-1/(3k)}$. Esto es implicado por la Conjetura de los Repunits Generalizada o la Hipótesis H de Schinzel.

2. Protocolos PIR Mejorados: Al integrar los nuevos polinomios dispersos en el marco de Ghasemi, Kopparty y Sudan (2025), los autores derivan un protocolo PIR de $s$ servidores con una complejidad de comunicación de:
   $$\exp(O((\log n)^{1/s} (\log \log n)^{1-1/s}))$$
   Esto es estrictamente mejor que los resultados previos del estado del arte para cualquier $s \ge 4$. Por ejemplo, mientras que trabajos previos requerían $2^k$ o $3k/2$ servidores para lograr una comunicación de $\exp(\tilde{O}((\log n)^{1/k}))$, este trabajo logra la misma comunicación con solo $k+1$ servidores (donde $s=k+1$).

3. Resultados Incondicionales para $s$ Pequeños: A través de la validación empírica, los autores demuestran que las condiciones de teoría de números requeridas se cumplen para valores pequeños de $k$. Específicamente, construyen protocolos PIR incondicionales de $s$ servidores para todo $s \in [2, 15]$. Asumiendo que los primos probables son realmente primos, esto se extiende a $s \in [2, 24]$.

4. Régimen de Servidores Superconstantes: El artículo analiza el régimen donde $s$ crece con $n$. Bajo una variante más fuerte de su conjetura, muestran que la complejidad de comunicación puede reducirse superpolinomialmente en comparación con las construcciones previas de PIR de vectores de coincidencia para $s \le \exp(o(\sqrt{\log \log n} / \log \log \log n))$. Sin embargo, para $s$ muy grandes, sus técnicas actualmente no ofrecen una mejora sobre las construcciones existentes.

5. Descubrimiento Asistido por IA: Los autores declaran explícitamente que el resultado principal (Teorema 1.2) y su prueba fueron descubiertos mediante una conversación con el modelo OpenAI GPT-5.5 Pro. El modelo identificó un marco general para construir los polinomios necesarios y lo generalizó a una prueba formal.

Significado
El artículo afirma resolver un problema abierto de larga data respecto a la dispersión mínima de los polinomios de decodificación $S$, optimizando así el compromiso entre comunicación y número de servidores en el marco de los vectores de coincencia. Al reducir el número de servidores requeridos para una dada complejidad de comunicación de exponencial en el exponente (por ejemplo, $2^k$) a lineal en el exponente ($k+1$), el trabajo mejora significativamente la eficiencia de los protocolos PIR. Los autores posicionan este trabajo como un paso definitivo dentro del paradigma actual de "vector de coincidencia + polinomio de decodificación", al tiempo que reconocen que mejoras adicionales podrían requerir nuevos marcos o diferentes mecanismos para la construcción de rejillas de raíces de la unidad. El trabajo también destaca el potencial de los modelos de IA en el descubrimiento de nuevas construcciones matemáticas y sus pruebas.