Chapter Summary

Chapter Summary

Key Points

• 1.

  Classical PIR hides the desired file index from $N$ replicated databases. The user retrieves one file from a $K$-file library; each database, seen in isolation, learns nothing about which file was requested. The trivial baseline (download everything) achieves rate $1/K$ but with no privacy beyond not revealing the requested-content; classical PIR achieves a strictly higher rate while preserving query privacy.

• 2.

  The Sun-Jafar capacity formula is $C_{\\text{PIR}} = (1 + 1/N + \\cdots + 1/N^{K-1})^{-1}$. It approaches $1$ as $N \\to \\infty$ (more databases = less overhead) and $1 - 1/N$ as $K \\to \\infty$ (more files = bounded asymptote). For typical $(N, K) = (4, 100)$: capacity $\\approx 0.75$.

• 3.

  Achievability via finite-field IA: the Sun-Jafar scheme uses a $K$-level XOR structure where each level cancels one layer of interferer file contributions. Each file is split into $N^K$ chunks; coordinated queries across the $N$ databases enable the user to reconstruct W_\\theta from a download of size $D = L \\cdot \\sum_{i=0}^{K-1} N^{-i}$.

• 4.

  Matching converse via cut-set: the four-step Chapter 2 recipe (cut, entropy bound, symmetrize, normalize) gives the lower bound, with a key inductive step on the file count $K$. Achievability and converse meet exactly at $C_{\\text{PIR}}$, closing the rate region of classical PIR.

• 5.

  Many extensions exist — coded storage, $T$-colluding, symmetric, cache-aided. Each trades off some constraint (storage cost, collusion threshold, two-sided privacy, side information) against the achievable rate. Chapter 14 develops the first three; Chapter 15 develops cache-aided PIR with a CommIT-relevant contribution on demand-private settings.