Prerequisites & Notation

Before You Begin

Chapter 13 opens Part IV with classical PIR — the Sun-Jafar capacity result. The chapter sits at the intersection of network information theory and applied cryptography. Prerequisites are Chapter 3's secret sharing and Chapter 4's finite-field interference alignment, plus basic information-theoretic fluency from Book ITA.

Finite-field IA (Chapter 4 §4.1, §4.4)(Review ch04)
Self-check: Why does finite-field IA achieve $K/2$ DoF in the $K$ -user interference channel?
Shamir secret sharing (Chapter 3 §3.2)(Review ch03)
Self-check: State the privacy guarantee of an $(t, n)$ -Shamir scheme in mutual-information terms.
Mutual information / data processing inequality(Review ch01)
Self-check: Restate $I(X; Y) \leq I(X; Z)$ for $Z$ a function of $Y$ .
Cut-set bounds (Chapter 2 §2.1)(Review ch02)
Self-check: Recall the four-step cut-set converse recipe.
Basic geometric series
Self-check: Sum: $\sum_{i = 0}^{K-1} x^i = (1 - x^K)/(1 - x)$ .

Notation for This Chapter

PIR uses different conventions from coded computing: $N$ now denotes the number of databases (not workers), and $K$ denotes the number of files (not the recovery threshold). Where collision with earlier chapters' usage occurs, we flag it explicitly.

Symbol	Meaning	Introduced
$N$	Number of databases (each storing all $K$ files)	s01
$K$	Number of files in the library (collision: $K$ = recovery threshold in Ch. 5)	s01
$L$	File length (in bits or symbols of $\mathbb{F}_q$ )	s01
$W_k$	The $k$ -th file, $k = 1, \ldots, K$	s01
$\theta$	The user's desired file index, $\theta \in [K]$ , uniformly random	s01
$Q^{(\theta, n)}$	Query sent by the user to database $n$ for desired index $\theta$	s01
$A^{(\theta, n)}$	Answer returned by database $n$ in response to $Q^{(\theta, n)}$	s01
$D$	Total download size (sum of all $A$ 's lengths)	s02
$R = L / D$	PIR rate (useful bits per downloaded bit)	s02
$C_{\text{PIR}}$	PIR capacity (supremum of achievable $R$ )	s02

← Ch 12 The PIR Problem and Threat Model