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

Technical Summary: Exponentially Fewer-Server PIR from Sparser $S$-Decoding Polynomials

Problem Statement
Private Information Retrieval (PIR) allows a user to retrieve an item from a database of size $n$ held by $s$ non-colluding servers without revealing the index of the item to any individual server. The primary goal is to minimize the total communication complexity. While trivial protocols require $O(n)$ communication, prior work established that for a constant number of servers $s$, communication could be reduced to sub-polynomial levels, specifically $\exp(\tilde{O}(\sqrt{\log n}))$ for $s=3$ (Efremenko, 2009) and $\exp(\tilde{O}((\log n)^{1/s}))$ for general $s$ under specific number-theoretic assumptions.

However, a significant gap remained in the trade-off between the number of servers $s$ and the communication complexity. Specifically, within the "matching vector + $S$-decoding polynomial" framework (pioneered by Efremenko and refined by Ghasemi, Kopparty, and Sudan), the best known constructions required $s = 2^k$ or $s = 3k/2$ servers to achieve communication $\exp(\tilde{O}((\log n)^{1/k}))$. Theoretical lower bounds by Ghasemi and Kopparty (2026) suggested that the sparsity of the necessary decoding polynomials could be as low as $k+1$, implying a potential for exponentially fewer servers for the same communication cost. The open problem was whether such optimally sparse polynomials could be constructed.

Methodology
The authors address this by focusing on the construction of $S$-decoding polynomials. Let $m = p_1 \dots p_k$ be a product of $k$ distinct primes, and let $S^*_m \subseteq \mathbb{Z}_m$ be the canonical set of residues congruent to 0 or 1 modulo each $p_i$. An $S^*_m$-decoding polynomial $P$ over a finite field $\mathbb{F}$ must satisfy $P(1)=1$ and $P(\gamma^j)=0$ for all $j \in S^*_m \setminus \{0\}$, where $\gamma$ is a primitive $m$-th root of unity. The sparsity of $P$ (number of non-zero coefficients) directly dictates the number of servers $s$ required in the PIR protocol.

The paper's core technical contribution is establishing an equivalence between the existence of an $S^*_m$-decoding polynomial of sparsity $k+1$ and the existence of a "root-of-unity grid." A root-of-unity grid is a configuration of elements $a_1, \dots, a_k \in \mathbb{F} \setminus \{0\}$ and distinct $t_1, \dots, t_{k+1} \in \mathbb{F}$ such that $1 + a_i t_j$ is a $p_i$-th root of unity for all $i, j$.

To construct these grids, the authors propose two approaches:

1. Probabilistic Method (Rough Repunits): This is the primary approach used for the main results. It relies on finding a prime $q$ and integers $d_1, \dots, d_k$ such that $q^{d_i}-1$ has a large prime factor (specifically, a "rough" number where the largest prime factor is at least $(q^{d_i}-1)^{1-1/(3k)}$). The existence of such numbers is guaranteed under a plausible number-theoretic conjecture.
2. Algebraic Method (Norm Kernels): A secondary approach using Galois theory and the norm map to construct grids, which successfully recovers Efremenko's original $m=7 \times 73$ example but does not generalize as broadly as the probabilistic method for the authors' main theorems.

For regimes where the number of servers $s$ grows with $n$ (superconstant), the authors employ a "stitching" technique (based on Itoh and Suzuki, 2010) to combine multiple root-of-unity grids over the same characteristic into a single decoding polynomial.

Key Contributions and Results

1. Resolution of the Sparsity Gap: Under a number-theoretic conjecture (Conjecture 1.1), the authors prove that for any constant $k$, there exists an $S^*_m$-decoding polynomial of sparsity $k+1$ where $m$ is a product of $k$ distinct primes. This matches the lower bound established by Ghasemi and Kopparty, completely closing the exponential gap between upper and lower bounds on sparsity.

   • Conjecture 1.1: For every $k>1$, there exists a prime $q \ge k+1$ and distinct integers $d_i \ge 6$ such that $q^{d_i}-1$ has a prime divisor $\ge (q^{d_i}-1)^{1-1/(3k)}$. This is implied by the Generalized Repunit Conjecture or Schinzel's Hypothesis H.

2. Improved PIR Protocols: By plugging the new sparse polynomials into the framework of Ghasemi, Kopparty, and Sudan (2025), the authors derive an $s$-server PIR protocol with communication complexity:
   $$\exp(O((\log n)^{1/s} (\log \log n)^{1-1/s}))$$
   This is strictly better than previous state-of-the-art results for any $s \ge 4$. For example, while previous works required $2^k$ or $3k/2$ servers to achieve communication $\exp(\tilde{O}((\log n)^{1/k}))$, this work achieves the same communication with only $k+1$ servers (where $s=k+1$).

3. Unconditional Results for Small $s$: Through empirical validation, the authors demonstrate that the required number-theoretic conditions hold for small values of $k$. Specifically, they construct unconditional $s$-server PIR protocols for all $s \in [2, 15]$. Assuming probable primes are actually prime, this extends to $s \in [2, 24]$.

4. Superconstant Server Regime: The paper analyzes the regime where $s$ grows with $n$. Under a stronger variant of their conjecture, they show that communication complexity can be superpolynomially reduced compared to prior matching-vector PIR constructions for $s \le \exp(o(\sqrt{\log \log n} / \log \log \log n))$. However, for very large $s$, their techniques do not currently offer an improvement over existing constructions.

5. AI-Assisted Discovery: The authors explicitly state that the main result (Theorem 1.2) and its proof were discovered via a conversation with OpenAI's GPT-5.5 Pro model. The model identified a general framework for constructing the necessary polynomials and generalized it to a formal proof.

Significance
The paper claims to resolve a long-standing open problem regarding the minimal sparsity of $S$-decoding polynomials, thereby optimizing the communication-server trade-off in the matching-vector PIR framework. By reducing the number of servers required for a given communication complexity from exponential in the exponent (e.g., $2^k$) to linear in the exponent ($k+1$), the work significantly improves the efficiency of PIR protocols. The authors position this as a definitive step within the current "matching vector + decoding polynomial" paradigm, while acknowledging that further improvements may require new frameworks or different mechanisms for constructing root-of-unity grids. The work also highlights the potential of AI models in discovering novel mathematical constructions and proofs.