Prerequisites & Notation

Before You Begin

Chapter 15 closes Part IV with PIR variants where the user has side information — typically a cache populated in a placement phase before the user knows which file they want. The chapter builds on Chapters 13-14 (classical and extended PIR) and connects to the coded-caching framework (Book CC). The CommIT group's contribution on demand-private cached delivery (Wan-Tuninetti-Caire 2021) appears in §15.3.

Sun-Jafar PIR capacity (Chapter 13)(Review ch13)
Self-check: State $C_{\text{PIR}}(N, K)$ and the role of $N$ vs. $K$ in the formula.
$T$ -colluding PIR (Chapter 14 §14.2)(Review ch14)
Self-check: How does the privacy threat model change from classical PIR to $T$ -colluding?
Coded caching: placement vs. delivery(Review ch01)
Self-check: Distinguish the placement (offline) and delivery (online) phases of a coded-caching protocol.
Mutual-information chain rule(Review ch01)
Self-check: Expand $I(X; Y, Z)$ in terms of conditional MI.
Cut-set converse recipe(Review ch02)
Self-check: Apply the four-step cut-set recipe to a retrieval problem with auxiliary state.

Notation for This Chapter

Chapter 15 inherits PIR notation from Chapters 13-14 and adds notation for side information and caches.

Symbol	Meaning	Introduced
$M$	Number of side-information (prefetched) files at the user	s01
$\mathcal{S}$	Set of indices of side-information files at the user, $\|\mathcal{S}\| = M$ , $\theta \notin \mathcal{S}$	s01
$Z$	User's cache content (in §15.2-§15.3)	s02
$\gamma$	Cache size, normalized: $\|Z\| = \gamma \cdot K \cdot L$	s02
$U$	Number of users in cached delivery (§15.3)	s03
$d_u$	Demand of user $u$ , $d_u \in [K]$ (§15.3)	s03
$C_{\text{PIR-SI}}(N, K, M)$	Capacity of PIR with $M$ side-info files	s01
$R^*(\gamma)$	Demand-private cached-delivery rate (§15.3)	s03

← Ch 14 PIR with Side Information