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

Resumo Técnico: Menos Servidores Exponencialmente para PIR de Polinômios de Decodificação $S$ mais Esparsos

Enunciado do Problema
A Recuperação de Informação Privada (PIR) permite que um usuário recupere um item de um banco de dados de tamanho $n$ mantido por $s$ servidores não colusivos sem revelar o índice do item a qualquer servidor individual. O objetivo principal é minimizar a complexidade total de comunicação. Enquanto protocolos triviais exigem $O(n)$ de comunicação, trabalhos anteriores estabeleceram que, para um número constante de servidores $s$, a comunicação poderia ser reduzida a níveis subpolinomiais, especificamente $\exp(\tilde{O}(\sqrt{\log n}))$ para $s=3$ (Efremenko, 2009) e $\exp(\tilde{O}((\log n)^{1/s})$ para $s$ geral sob suposições numéricas específicas.

No entanto, uma lacuna significativa permanecia na relação entre o número de servidores $s$ e a complexidade de comunicação. Especificamente, dentro da estrutura "vetor de correspondência (matching vector) + polinômio de decodificação $S$" (iniciada por Efremenko e refinada por Ghasemi, Kopparty e Sudan), as melhores construções conhecidas exigiam $s = 2^k$ ou $s = 3k/2$ servidores para alcançar comunicação $\exp(\tilde{O}((\log n)^{1/k}))$. Limites teóricos inferiores por Ghasemi e Kopparty (2026) sugeriram que a esparsidade dos polinômios de decodificação necessários poderia ser tão baixa quanto $k+1$, implicando o potencial para exponencialmente menos servidores para o mesmo custo de comunicação. O problema em aberto era se tais polinômios otimamente esparsos poderiam ser construídos.

Metodologia
Os autores abordam isso focando na construção de polinômios de decodificação $S$. Seja $m = p_1 \dots p_k$ um produto de $k$ primos distintos, e seja $S^*_m \subseteq \mathbb{Z}_m$ o conjunto canônico de resíduos congruentes a 0 ou 1 módulo cada $p_i$. Um polinômio de decodificação $S^*_m$, denotado por $P$, sobre um corpo finito $\mathbb{F}$, deve satisfazer $P(1)=1$ e $P(\gamma^j)=0$ para todo $j \in S^*_m \setminus \{0\}$, onde $\gamma$ é uma raiz da unidade primitiva de ordem $m$. A esparsidade de $P$ (número de coeficientes não nulos) dita diretamente o número de servidores $s$ necessários no protocolo PIR.

A principal contribuição técnica do artigo é estabelecer uma equivalência entre a existência de um polinômio de decodificação $S^*_m$ de esparsidade $k+1$ e a existência de uma "grade de raízes da unidade" (root-of-unity grid). Uma grade de raízes da unidade é uma configuração de elementos $a_1, \dots, a_k \in \mathbb{F} \setminus \{0\}$ e $t_1, \dots, t_{k+1}$ distintos em $\mathbb{F}$ tal que $1 + a_i t_j$ é uma raiz da unidade de ordem $p_i$ para todo $i, j$.

Para construir essas grades, os autores propõem duas abordagens:

1. Método Probabilístico (Repunits Grosseiros/Rough Repunits): Esta é a abordagem principal utilizada para os resultados principais. Ela se baseia em encontrar um primo $q$ e inteiros $d_1, \dots, d_k$ tais que $q^{d_i}-1$ possua um fator primo grande (especificamente, um número "grosseiro" onde o maior fator primo é pelo menos $(q^{d_i}-1)^{1-1/(3k)}$). A existência de tais números é garantida sob uma conjectura de teoria dos números plausível.
2. Método Algébrico (Núcleos de Norma/Norm Kernels): Uma abordagem secundária usando teoria de Galois e o mapa de norma para construir grades, que recupera com sucesso o exemplo original de Efremenko $m=7 \times 73$, mas não se generaliza tão amplamente quanto o método probabilístico para os principais teoremas dos autores.

Para regimes onde o número de servidores $s$ cresce com $n$ (superconstante), os autores empregam uma técnica de "costura" (baseada em Itoh e Suzuki, 2010) para combinar múltiplas grades de raízes da unidade sobre o mesmo caráter em um único polinômio de decodificação.

Principais Contribuições e Resultados

1. Resolução da Lacuna de Esparsidade: Sob uma conjectura de teoria dos números (Conjectura 1.1), os autores provam que, para qualquer constante $k$, existe um polinômio de decodificação $S^*_m$ de esparsidade $k+1$, onde $m$ é um produto de $k$ primos distintos. Isso iguala o limite inferior estabelecido por Ghasemi e Kopparty, fechando completamente a lacuna exponencial entre limites superiores e inferiores de esparsidade.

   • Conjectura 1.1: Para todo $k>1$, existe um primo $q \ge k+1$ e inteiros distintos $d_i \ge 6$ tais que $q^{d_i}-1$ possui um divisor primo $\ge (q^{d_i}-1)^{1-1/(3k)}$. Isso é implicado pela Conjectura de Repunit Generalizada ou pela Hipótese H de Schinzel.

2. Protocolos PIR Melhorados: Ao inserir os novos polinômios esparsos na estrutura de Ghasemi, Kopparty e Sudan (2025), os autores derivam um protocolo PIR de $s$ servidores com complexidade de comunicação:
   $$\exp(O((\log n)^{1/s} (\log \log n)^{1-1/s}))$$
   Isso é estritamente melhor que os resultados anteriores de estado da arte para qualquer $s \ge 4$. Por exemplo, enquanto trabalhos anteriores exigiam $2^k$ ou $3k/2$ servidores para alcançar comunicação $\exp(\tilde{O}((\log n)^{1/k}))$, este trabalho alcança a mesma comunicação com apenas $k+1$ servidores (onde $s=k+1$).

3. Resultados Incondicionais para Pequenos $s$: Através de validação empírica, os autores demonstram que as condições de teoria dos números necessárias sustentam-se para pequenos valores de $k$. Especificamente, eles constroem protocolos PIR incondicionais de $s$ servidores para todos os $s \in [2, 15]$. Assumindo que primos prováveis são de fato primos, isso se estende para $s \in [2, 24]$.

4. Regime de Servidores Superconstantes: O artigo analisa o regime onde $s$ cresce com $n$. Sob uma variante mais forte de sua conjectura, eles mostram que a complexidade de comunicação pode ser reduzida superpolinomialmente em comparação com as construções anteriores de PIR de vetor de correspondência para $s \le \exp(o(\sqrt{\log \log n} / \log \log \log n))$. No entanto, para $s$ muito grande, suas técnicas não oferecem atualmente melhorias sobre as construções existentes.

5. Descoberta Assistida por IA: Os autores declaram explicitamente que o resultado principal (Teorema 1.2) e sua prova foram descobertos via uma conversa com o modelo OpenAI GPT-5.5 Pro. O modelo identificou um framework geral para construir os polinômios necessários e o generalizou para uma prova formal.

Significância
O artigo afirma resolver um problema de longa data sobre a esparsidade mínima de polinômios de decodificação $S$, otimizando a relação de troca (trade-off) entre comunicação e servidores no framework de PIR de vetor de correspondência. Ao reduzir o número de servidores necessários para uma dada complexidade de comunicação de exponencial no expoente (ex: $2^k$) para linear no expoente ($k+1$), o trabalho melhora significativamente a eficiência dos protocolos PIR. Os autores posicionam este trabalho como um passo definitivo dentro do paradigma atual de "vetor de correspondência + polinômio de decodificação", ao mesmo tempo em que reconhecem que melhorias futuras podem exigir novos frameworks ou mecanismos diferentes para a construção de grades de raízes da unidade. O trabalho também destaca o potencial de modelos de IA na descoberta de novas construções matemáticas e provas.