Private Information Retrieval from Joint Systematic MDS-Coded with Non-Colluding Servers: Bounds and Constructions

技術要約：非共謀サーバーを用いた結合系統的MDS符号化によるプライベート情報検索

問題提起
本論文は、$M$ 個のファイルが $[N, K]$ 最大距離分離（MDS）符号を用いて $N$ 個の非共謀サーバーに分散格納されている分散ストレージシステムにおける、プライベート情報検索（PIR）の問題を扱う。各ファイルを独立して符号化する従来の「分離型」MDS符号化PIRスキームとは異なり、本研究では結合MDS符号化PIRに焦ብしている。このモデルでは、すべての $M$ 個のファイルが単一のコードワードへと一括して符号化される系統的MDSアレイコードを使用する。ユーザーは、個々のサーバーに対してインデックス $\theta$ の正体を明かすことなく、特定のファイル $W_\theta$ を取得することを目的とする。

主な動機は、SunおよびTian [28] による、特定のパラメータ領域において結合符号化が分離型MDS符号化PIR（BanawanおよびUlukus [9] によって確立されたもの）の容量限界を打破できるという観察に基づいている。しかし、結合MDS符号化PIRの理論的な容量は、特にストレージパターンや系統的制約が取得レートにどのように影響するかという点において、これまでほとんど解明されていなかった。

手法とシステムモデル
著者らは、以下の2つの重要な要素を導入することでシステムモデルを精緻化している：

1. ストレージパターン ($P$): ストレージコードの $K$ 個の系統的入力ブロックに $M$ 個のファイルがどのように配置されるかを示す行列。
2. 系統的MDSアレイコード ($C$): これらのブロックを $N$ 個のサーバーに符号化するコード。

本論文では、固定されたストレージパターン $P$ に対して、適合するすべての系統的MDSアレイコードに対する取得レートの上限を容量 $C^{(s)}_{JMDS-PIR}(M, N, K, P)$ と定義する。研究では、以下の2つの特定のストレージパターンに焦点を当てる：

• ケース1: $K = Mt$で、パターン$P = \ell I_M \otimes \mathbf{1}_t$。
• ケース2: $K = Mt + 1$で、パターン$P = \frac{\ell}{M} (M I_M \otimes \mathbf{1}_t \mid \mathbf{1}_M^\top)$。

理論的限界を導出するために、著者らは情報理論的ツール、具体的にはサーバーの回答の条件付き独立構造の特性化（補題3）およびHanの不等式に基づく再帰的不等式の導出（補題5および8）を用いている。構成においては、プライバシーを確保しつつ有用な情報のダウンロードを最大化するために、ランダムな置換と格納されたシンボルの線形結合を利用している。

主要な貢献と結果

1. 容量の上限:

   • **$K = Mt$** かつパターン$P = \ell I_M \otimes \mathbf{1}_t$の場合、著者らは$1 - (1 - \frac{1}{M})\frac{K}{N}$ という上限を導出した。
   • **$K = Mt + 1$** かつパターン$P = \frac{\ell}{M} (M I_M \otimes \mathbf{1}_t \mid \mathbf{1}_M^\top)$の場合、著者らは$\frac{K(N-K+t)}{(K-1)(N-1)}$ という上限を導出した。
   • 決定的なことに、$K = Mt$かつ$N \le K + t$ の場合、導出された上限はSunおよびTian [28] によって提案されたスキームの性能と一致しており、これらの特定のストレージパターンにおけるそれらの最適性を証明する初の証拠となった。

2. スキームの構成:
   本論文は、3つの結合系統的MDS符号化PIRスキームを構築している：

   • 構成1 ($N \le K + t, K = Mt$): このスキームは上限 $1 - (1 - \frac{1}{M})\frac{K}{N}$ を達成し、これによりこの領域における正確な容量を確立する。
   • **構成2 ($N > K + t, K = Mt$):** このスキームは$\frac{N+K-t}{NM}$ の取得レートを達成する。
   • 構成3 ($N \le K + t, K = Mt + 1$): このスキームは $\frac{K(N-K+t)}{M((t+1)N-K)}$ の取得レートを達成する。

3. 性能向上:
   提案されたスキームを、容量達成型の分離型MDS符号化PIR（例：[9], [17], [18]）と比較した。分析の結果、結合スキームは特定のパラメータ範囲において、厳密に高い取得レートを達成することが示された：

   • $K = Mt$の場合、ストレージレート$r = K/N$ が高いときに顕著な改善が見られる。
   • $K = Mt + 1$の場合、結合スキームは$K < N \le K + t$ において常に分離型スキームを上回る。
   • 定量的利得: 相対的な取得レートの改善は、$M \ge 4$ のとき**15%を超え、$M \ge 9$ のとき20%**を超え、$M$ が増加するにつれて漸近的に $1 - 2/e \approx 26.42\%$ に近づく。
   • さらに、提案された構成は、従来の結合スキーム [28] と比較して、より小さなファイルサイズを必要とし、場合によっては（例：$M=2, N=3t$）、必要な有限体のサイズを大幅に削減できる。

意義
本論文の主な意義は、規定されたストレージパターンの下での結合系統的MDS符号化PIRの容量を理論的に特徴付けた点にあり、これはこれまで未解決の問題であった。特定のパラメータにおけるSunおよびTian [28] のスキームの最適性を証明し、より広いパラメータセットのための新しい構成を提供することで、本研究は、結合符号化が単なるヒューリスティックではなく、分散ストレージにおけるPIRのための証明可能な優れた戦略であることを示している。結果は、結合MDS符号化PIRが分離型符号化の容量限界を打破できることを裏付けており、ファイル数（$M$）が増加するにつれて、プライバシーを損なうことなく取得効率を大幅に向上させることを示している。著者らは、自らの結果は特定のパラメータ領域をカバーしているものの、より一般的な結合MDS符号化PRLの設定へこれらの知見を拡張することは、今後の課題として困難な方向性であると述べている。