Prerequisites & Notation

Before You Begin

Chapter 14 extends classical PIR (Chapter 13) along three orthogonal axes: coded storage instead of replication (§14.1), $T$ -colluding databases (§14.2), and two-sided privacy via SPIR (§14.3). Section §14.4 sketches what is known when these extensions are combined. Each section relies on the same finite-field IA core as Chapter 13 — the novelty is in how the constraints alter the achievable rate region.

Sun-Jafar PIR capacity (Chapter 13 §13.3)(Review ch13)
Self-check: State the formula $C_{\text{PIR}}(N, K)$ and identify each term's role.
MDS codes and Singleton bound (background)(Review ch04)
Self-check: For an $(n, k)$ -MDS code, what is the minimum distance, and how many erasures can be corrected?
Shamir secret sharing (Chapter 3)(Review ch03)
Self-check: Why does the $T$ -private constraint force polynomial degree $\geq T$ in Shamir-type schemes?
Cut-set converse recipe (Chapter 2)(Review ch02)
Self-check: Apply the four-step recipe (cut → entropy bound → symmetrize → normalize) to a generic retrieval problem.
Mutual-information chain rule(Review ch01)
Self-check: Expand $I(X; Y, Z)$ using the chain rule.

Notation for This Chapter

Chapter 14 inherits the PIR notation from Chapter 13 ( $N$ databases, $K$ files, $\theta$ desired index) and adds:

Symbol	Meaning	Introduced
$r$	MDS-code dimension: any $r$ databases reconstruct the full library	s01
$T$	Maximum colluding subset size; privacy holds against any $T$ databases	s02
$\mathcal{T}$	An arbitrary subset of $[N]$ with $\|\mathcal{T}\| \leq T$	s02
$C_{\text{PIR-MDS}}(N, K, r)$	Capacity for $(N, r)$ -MDS coded-storage PIR	s01
$C_{\text{PIR}}(N, K, T)$	Capacity for $T$ -colluding PIR with replicated storage	s02
$C_{\text{SPIR}}(N, K)$	Capacity for symmetric PIR (two-sided privacy)	s03
$S$	Common randomness shared across databases (used in SPIR)	s03
$H(\cdot)$	Shannon entropy	s03

← Ch 13 Coded-Storage PIR