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

技術要約：より疎な $S$-復号多項式による指数関数的に少ないサーバー数でのPIR

問題提起
プライベート情報検索（PIR）は、ユーザーがデータベースのサイズ $n$ のアイテムを、非共謀の $s$ 個のサーバーから、個々のサーバーに対してインデックスを明かすことなく取得することを可能にする。主な目標は、総通信量を最小化することである。自明なプロトコルは $O(n)$ の通信を必要とするが、先行研究では、定数個のサーバー $s$ に対して、通信量を劣多項式レベル、具体的には $s=3$ の場合は $\exp(\tilde{O}(\sqrt{\log n}))$、および特定の数論的仮定の下での一般的な $s$ に対しては $\exp(\tilde{O}((\log n)^{1/s}))$ まで削減できることが確立されている。

しかし、サーバー数 $s$ と通信量のトレードオフにおいて、大きなギャップが残っていた。具体的には、「マッチングベクトル + $S$-復号多項式」のフレームワーク（Efremenkoによって開かれ、Ghasemi, Kopparty, and Sudanによって洗練されたもの）において、通信量 $\exp(\tilde{O}((\log n)^{1/k}))$ を達成するために、従来は $s = 2^k$ または $s = 3k/2$ 個のサーバーを必要としていた。Ghasemi and Kopparty (2026) による理論的な下界は、必要な復号多項式の疎さが $k+1$ まで低くなり得ることを示唆しており、これは、同じ通信コストに対して指数関数的に少ないサーバー数で実現できる可能性を意味していた。未解決の問題は、このような最適に疎な多項式を構築できるか否かであった。

手法
著者らは、$S$-復号多項式の構築に焦点を当てることでこの問題に取り組む。$m = p_1 \dots p_k$ を $k$ 個の異なる素数の積とし、$S^*_m \subseteq \mathbb{Z}_m$ を各 $p_i$ に対して 0 または 1 に合同な剰余の標準的な集合とする。有限体 $\mathbb{F}$ 上の $S^*_m$-復号多項式 $P$ は、$P(1)=1$ かつ すべての $j \in S^*_m \setminus \{0\}$ に対して $P(\gamma^j)=0$（ここで $\gamma$ は原始 $m$ 乗根）を満たさなければならない。$P$ の疎さ（非ゼロ係数の数）は、PIRプロトコルに必要なサーバー数 $s$ を直接的に決定する。

本論文の核心となる技術的貢献は、$S^*_m$-復号多項式の存在と「1の冪根グリッド（root-of-unity grid）」の存在との間の等価性を確立することである。1の冪根グリッドとは、要素 $a_1, \dots, a_k \in \mathbb{F} \setminus \{0\}$ と、互いに異なる $t_1, \dots, t_{k+1} \in \mathbb{F}$ の構成であり、$1 + a_i t_j$ がすべての $i, j$ に対して $p_i$ 乗根となるものである。

これらのグリッドを構築するために、著者らは2つのアプローチを提案している：

1. 確率的手法（粗いレピュニット / Rough Repunits）： これは主要な結果に使用される主要なアプローチである。これは、素数 $q$ と整数 $d_1, \dots, d_k$ を見つけることに依存しており、それらは $q^{d_i}-1$ が大きな素因数（具体的には、最大の素因数が $(q^{d_i}-1)^{1-1/(3k)}$ 以上である「粗い」数）を持つ必要がある。このような数の存在は、妥当な数論的予想の下で保証されている。
2. 代数的手法（ノルム核 / Norm Kernels）： ガロア理論とノルム写像を用いた二次的なアプローチであり、Efremenkoの元の例である $m=7 \times 73$ を正常に復元しているが、著者の主要な定理のように広く一般化することはできない。

サーバー数 $s$ が $n$ と共に増大する（超定数）領域では、著者らは複数の1の冪根グリッドを同一の標数上の単一の復号多項式に結合するための「ステッチング（stitching）」技術（Itoh and Suzuki, 2010に基づく）を採用している。

主要な貢献と結果

1. 疎さのギャップの解消： 数論的予想（Conjecture 1.1）の下で、著者らは、任意の定数 $k$ に対して、$m$ が $k$ 個の異なる素数の積であるような、疎さが $k+1$ の $S^*_m$-復号多項式が存在することを証明した。これは、Ghasemi and Kopparty によって確立された下界と一致しており、疎さに関する上界と下界の間の指数関数的なギャップを完全に閉じたものである。

   • Conjecture 1.1: すべての $k>1$ に対して、素数 $q \ge k+1$ と異なる整数 $d_i \ge 6$ が存在し、$q^{d_i}-1$ は $\ge (q^{d_i}-1)^{1-1/(3k)}$ である素因数を持つ。これは、一般化レピュニット予想またはSchinzelの仮説Hによって示唆される。

2. 改良されたPIRプロトコル： 新しい疎な多項式をGhasemi, Kopparty, and Sudan (2025) のフレームワークに組み込むことで、著者らは以下の通信量を持つ $s$-サーバーPIRプロトコルを導出した：
   $$\exp(O((\log n)^{1/s} (\log \log n)^{1-1/s}))$$
   これは、任意の $s \ge 4$ において、従来の最先端の結果よりも厳密に優れている。例えば、従来の作業では $\exp(\tilde{O}((\log n)^{1/k}))$ の通信量を達成するために $2^k$ または $3k/2$ 個のサーバーを必要としたが、本研究では $s=k+1$ の場合にのみ $k+1$ 個のサーバーで同じ通信量を達成できる。

3. 小さな $s$ に対する無条件の結果： 実証的な検証を通じて、著者らは要求される数論的条件が小さな $k$ に対して成立することを示している。具体的には、すべての $s \in [2, 15]$ に対して無条件の $s$-サーバーPIRプロトコルを構築した。おそらく素数（probable primes）が実際に素数であると仮定すれば、これは $s \in [2, 24]$ まで拡張される。

4. 超定数サーバー領域： 本論文では、$s$ が $n$ と共に増大する領域についても分析している。より強力な変種の予想の下で、通信量が $s \le \exp(o(\sqrt{\log \log n} / \log \log \log n))$ に対して、従来のマッチングベクトルPIR構成と比較して超多項式的に削減されることを示している。ただし、非常に大きな $s$ に対しては、現在の彼らの手法は既存の構成に対する改善を提供していない。

5. AI支援による発見： 著者らは、主要な結果（Theorem 1.2）とその証明が、OpenAIのGPT-5.5 Proモデルとの対話を通じて発見されたことを明示している。モデルは、必要な多項式を構築するための一般的なフレームワークを特定し、それを形式的な証明へと一般化した。

意義
本論文は、マッチングベクトルPIRの枠組みにおける、 $S$-復号多項式の最小の疎さに関する長年の未解決問題を解決したと主張しており、通信量とサーバー数のトレードオフを最適化している。通信量に対するサーバー数の必要量を、指数の指数（例：$2^k$）から、指数の線形（$k+1$）へと減少させることで、本研究はPIRプロトコルの効率を大幅に向上させている。著者らは、本研究を現在の「マッチングベクトル + 復号多項式」パラダイム内における決定的な一歩として位置づけており、さらなる改善には新しいフレームワークや1の冪根グリッドを構築するための異なるメカニズムが必要になる可能性があることを認めている。また、本研究は、数学的な新しい構成や証明の発見におけるAIモデルの可能性を浮き彫りにしている。