Chapter Summary

Chapter 14 Summary

Key Points

• 1.

  Coded-storage PIR (§14.1): Sun-Jafar generalizes to $(N, r)$-MDS coded storage with capacity $C_{\text{PIR-MDS}}(N, K, r) = (\sum_{i=0}^{K-1}(r/N)^i)^{-1}$ (Tajeddine–El Rouayheb 2018). Storage drops by factor $r$, rate decreases as $r$ grows. The asymptotic limit is $1 - r/N$.

• 2.

  $T$-colluding PIR (§14.2): replicated storage with privacy against any $T$ colluding databases gives capacity $C_{\text{PIR}}(N, K, T) = (\sum_{i=0}^{K-1}(T/N)^i)^{-1}$ (Sun–Jafar 2018). Achievability uses Shamir-style $(T, N)$-sharing of queries; $T = 1$ recovers classical, $T = N$ collapses to the trivial $1/K$.

• 3.

  SPIR (§14.3): two-sided privacy gives capacity $C_{\text{SPIR}}(N, K) = 1 - 1/N$ — independent of $K$. Requires shared randomness $H(S) \geq L/(N-1)$ across databases. The $K$-independence reflects the database-privacy decoupling.

• 4.

  Joint extensions (§14.4): combining constraints costs rate non-additively. Coded-storage + $T$-colluding has achievable rate (Freij-Hollanti) but capacity is open for general $K$. SPIR + coded-storage is settled at $1 - r/N$ (Wang–Skoglund 2019).

• 5.

  Operational guidance: pick the minimum constraint set for the actual threat model. Composition costs rate; three-plus extensions usually infeasible. Verify feasibility (e.g., $r + T - 1 < N$) before deployment.