Chapter 13: Classical Private Information Retrieval

Learning Objectives

• Formalize the classical PIR problem: $N$ replicated databases, $K$ files, retrieval without revealing the desired file index
• Construct the Sun–Jafar capacity-achieving PIR scheme via finite-field interference alignment
• Prove the PIR capacity formula $C_{\text{PIR}} = (1 + 1/N + \cdots + 1/N^{K-1})^{-1}$ achievability + matching converse
• Compare PIR with the trivial baseline (download everything: rate $1/K$) and quantify the savings
• Recognize PIR as a specialization of the finite-field IA framework from Chapter 4