Exercises

$C_{\text{PIR-SI}}(5, 8, 3) = C_{\text{PIR}}(5, 5) = (1 + 1/5 + 1/25 + 1/125 + 1/625)^{-1} = 625/781 \approx 0.800$.

$C_{\text{PIR}}(5, 8) \approx 0.800$ as well — the gap is tiny because $K \geq 5$ is already in the asymptotic regime.

$\mathbb{E}[I] = (K-1)\gamma = 7 \cdot 0.5 = 3.5$. Effective $K - I \approx 4.5$.

$C(4, 4.5) \approx C(4, 5) \approx 0.802$ (using interpolation; exact value slightly higher with the full mixture).

Cache fraction $\gamma = 0.5$ doubles the effective per-bit rate compared with $\gamma = 0$ — non-trivial improvement.

$R_{\text{MAN}} = 5 \cdot 0.6 / (1 + 2) = 3 / 3 = 1$.

$R^* = 5 \cdot 0.6 = 3$.

$R^* / R_{\text{MAN}} = 3 / 1 = 3$. Demand privacy costs $3\times$ rate.

$M = 0$: $C(4, 10) \approx 0.750$. $M = 9 = K - 1$: $C(4, 1) = 1$ (only one file to retrieve, trivially).

$M = 5$: $C(4, 5) \approx 0.802$. Slow growth from $M = 0$ to $M = 5$; rapid growth from $M = 5$ to $M = 9$.

Side info is most useful at the high-$M$ end of the spectrum. Small caches give small rate gains; nearly-full caches give dramatic gains (rate $\to 1$).

$C_{\text{PIR-SI}}(4, 10, 5) = C(4, 5) \approx 0.802$.

Binomial mixture centered around $i = 4-5$. Effective $K \approx 5-6$. $C \approx 0.83-0.85$ (slightly higher than $0.802$).

The cache spreads the side info across all $K$ files (half a bit per file, on average). This avoids "wasting" cache on files that won't be requested. Side info with $M$ complete files is less flexible — if $\theta \notin \mathcal{S}$, the protocol must retrieve a complete missing file.

For random caches with no popularity bias, cache-aided PIR is the right framework. For explicit knowledge of which files are wanted (e.g., personal favorites), side-info framework with $M$ complete files is appropriate.

$R^*(\gamma) = U(1 - \gamma)$. As $\gamma \to 1$, $R^* \to 0$.

At $\gamma = 1$, every user has the entire library in their cache. No delivery is needed. Demand privacy is automatically satisfied (the server doesn't broadcast anything, so it learns nothing about demands).

Cache-rich deployments (e.g., $\gamma > 0.9$) have near-zero delivery cost regardless of privacy. The privacy cost $R^* / R_{\text{MAN}} = 1 + U\gamma$ is dominated by the asymptotic $\gamma$.

$C(4, x) = (1 - 1/4)/(1 - (1/4)^x) = 0.75 / (1 - 4^{-x})$. Need $0.75 / (1 - 4^{-x}) \geq 0.95$, i.e., $1 - 4^{-x} \leq 0.789$, i.e., $4^{-x} \geq 0.211$, i.e., $x \leq -\log_4(0.211) \approx 1.12$.

$K - (K-1)\gamma = 10 - 9\gamma \leq 1.12$ $\Rightarrow \gamma \geq 8.88/9 \approx 0.987$.

At $\gamma = 0.99$, the cache holds $\sim 99\%$ of every file. Effective $K - I \approx 1$. Rate $\approx 1$. Plausible.

Reaching rate $0.95$ requires a very large cache (essentially 99% of the library at $K = 10$). Smaller caches give smaller improvements.

$R^*/R_{\text{MAN}} = 1 + U\gamma = 1 + 0.5 U$.

$U = 1$: ratio $= 1.5$. $U = 5$: ratio $= 3.5$. $U = 10$: ratio $= 6$. $U = 20$: ratio $= 11$. Linear in $U$.

For deployments with many users ($U \geq 10$), demand privacy becomes very expensive ($\geq 6\times$ rate cost). For small user populations ($U \leq 3$), the cost is $\leq 2.5\times$ — manageable.

$C(N, K - 0, T) = C(N, K, T)$ — recovers $T$-colluding PIR.

$C(N, K - M, 1) = C_{\text{PIR-SI}}(N, K, M)$ — recovers Wei-Banawan-Ulukus.

$C(N, K - (K-1), 1) = C(N, 1, 1) = 1$ — only one unknown file, capacity 1. Consistent with §15.1.

The conjecture is consistent with all known special cases. General proof is open (achievability follows easily; converse requires the joint cut-set argument, which has not been fully verified).

Each user $u$ decodes $W_{d_u}$ from $X$ (broadcast) and $Z_u$ (cache). Demand privacy: $X$ is independent of $\mathbf{d}$.

Apply cut-set: each user must be able to recover their requested file. $H(W_{d_u} | X, Z_u) = 0$ (decoding). $H(Z_u) \leq \gamma K L$ (cache size).

Demand privacy: $X$ is statistically independent of $\mathbf{d}$. The broadcast must be "demand-agnostic" — i.e., contain enough information to satisfy any demand vector simultaneously.

For $X$ to enable $U$ different users to recover any of $K$ possible files, given caches of size $\gamma K L$, we need $|X| \geq U(1 - \gamma) L$ bits. Because $X$ is demand-agnostic (privacy), we cannot use coded multicast (which would tailor $X$ to the specific demands).

$R^*(\gamma) = D / L \geq U(1 - \gamma)$. Achievability via the trivial uncoded scheme matches the bound.

$R(N, K, r, \gamma) = \sum_{i=0}^{K-1} \binom{K-1}{i} \gamma^i (1-\gamma)^{K-1-i} \cdot C_{\text{PIR-MDS}}(N, K-i, r)$ — same binomial structure with coded-storage capacity replacing classical PIR capacity.

$\gamma = 0$: $R = C_{\text{PIR-MDS}}(N, K, r)$ — coded-storage PIR. ✓ $r = 1$: $R = C_{\text{cache-PIR}}(N, K, \gamma)$ — uncoded-storage cache-aided PIR. ✓ $\gamma = 1$: $R = 1$ (everything cached). ✓

Conjecture is consistent with all boundary cases. Open: whether the binomial-mixture formula matches the capacity (converse is non-trivial for coded storage with caches).

Public-coin: each user generates their own randomness independently. No shared random masks between server and users (or among users).

Each user can mask their query with individual randomness. The server's broadcast may need to accommodate $U$ different randomness sources.

Open question. Heuristically, the rate may degrade by an additive factor proportional to $U$ (one extra "side channel" per user). Sharp characterization unknown.

Public-coin protocols are easier to deploy (no shared-key infrastructure) but typically incur a rate cost. Trade-off: deployment ease vs. rate efficiency.

Uniform demands: $H(\mathbf{d}) = U \log K$. WTC rate: $R^* = U(1 - \gamma)$.

Zipf ($\alpha = 1$, $K$ files): $H(\mathbf{d}) \approx U \cdot \log H_K \approx U \log \log K$ (Zipf entropy grows slowly).

With less demand entropy, the demand-privacy constraint is easier to satisfy — the optimal rate may be lower than $U(1 - \gamma)$. Open question: how much lower?

For popularity-driven workloads (e.g., video streaming), the WTC rate may be a pessimistic upper bound on the actual cost. Practical schemes can exploit the Zipf structure to recover some of the lost coded-multicast gain — but only at the cost of partial demand privacy.

Query 1: classical PIR rate $C(N, K)$. Query 2 (with $W_{\theta_1}$ as side info): rate $C(N, K - 1)$. ... Query $t$: rate $C(N, K - t + 1)$ (assuming all $\theta$'s distinct).

Average $R_T = (1/T) \sum_{t=1}^{T} C(N, K - t + 1)$. As $T \to K$, this approaches $1$ (the user eventually has the entire library).

One-shot capacity: $C(N, K) \approx 1 - 1/N$. Amortized rate over $T = K$ queries: avg $\approx (1/K) \sum_{k=1}^{K} C(N, k)$, which exceeds the one-shot capacity (because later queries enjoy effective-$K$ reduction).

Latency amortization is a real practical advantage of repeat queries. The "first query is expensive, later queries cheap" pattern is intuitive. Sharp characterization is open.

Classical Sun-Jafar: $C(N, K) \to 1 - 1/N$ as $K \to \infty$. This is bounded above by the download-rate constraint.

Quantum entanglement between databases (or between user and databases) can enable more efficient interference alignment. Analog: superdense coding sends $2$ bits in $1$ qubit — quantum PIR may transmit more "information per query" per qubit.

Recent work (Song-Kao-Hayashi 2019; Allaix-Cascudo-Cuevas-Bardo 2020) establishes quantum PIR capacity in some regimes — sometimes exceeding the classical capacity. The full quantum PIR capacity is open.

Quantum PIR is one of the most exciting frontiers — the classical-quantum gap is non-trivial and still being characterized. Analogous gaps emerge in quantum coded computing (Chapter 18 may touch on this).

Quantum PIR requires quantum databases and quantum links — currently impractical. The results are theoretical benchmarks, not deployment targets.