Exercises

For the shared-link coded caching problem with $K$ users, $N$ files, per-user cache $M$, demand privacy ($I(\mathbf{d}_{-k}; X, \mathcal{Z}_k | d_k) = 0$) is achievable at the non-private MAN rate $R = K(1-M/N)/(1+KM/N)$. Shared randomness $O(K \log N!)$ bits per round suffices.

$I(\mathbf{d}_{-k}; X_{\mathbf{d}}, \mathcal{Z}_k) = H(\mathbf{d}_{-k}) = 9 \log_2 100 \approx 60$ bits/round. User $k$ learns ~60 bits about the 9 other users' demands. With Wan-Caire private scheme: 0 bits.

Information-theoretic privacy: adversary has unbounded computation; security provably impossible to break. Cryptographic privacy: adversary limited to polynomial time; security assumes hardness of some math problem (factoring, etc.). Quantum computers can break current cryptographic schemes; IT privacy is unaffected. Post-quantum applications prefer IT privacy.

Let $\mu = 0.1$: $R_0 = 20 \cdot 0.9/(1 + 2) = 6$. $R_5 = 15 \cdot 0.9/(1 + 1.5) = 5.4$. Penalty: 10%. Modest for practical $z$ values.

Placement happens during off-peak when delivery bandwidth is underutilized. Distributing shared-randomness keys (via PKI, SIM, etc.) can piggyback on placement bandwidth. Delivery-phase rate is unaffected by this one-time setup cost.

User $k$ receives XOR message $X = W_{\tilde d_1, \mathcal{S}_1} \oplus \ldots$ where $\tilde d_j = \pi_j(d_j)$.

User $k$ knows $\pi_k$ and $d_k$, so knows $\tilde d_k$. Its target subfile is $W_{\tilde d_k, \mathcal{S}_{-k}}$. The other summands involve $\tilde d_j$ for $j \neq k$ — which user $k$ does not know. BUT: user $k$ has all cached subfiles indexed by sets containing $k$, across all possible $\tilde d_j$ values. MAN's cache structure ensures that user $k$ can XOR out any summand whose index set contains $k$. Since user $k$ caches $W_{n, \mathcal{S}}$ for all $n \in [N]$ (every file's subfile with index containing $k$), it can perform the cancellation without knowing specific $\tilde d_j$ values.

Correctness preserved. Privacy preserved (doesn't learn $\tilde d_j$ values).

$R(z)/R(0) = (K-z)(1+K\mu)/(K(1+(K-z)\mu))$.

For $\mu = 0.1, K = 50$: $z = 0$: 1.00 (baseline). $z = 10$ (20%): 0.95. $z = 25$ (50%): 0.80. $z = 40$ (80%): 0.46. $z = 49$: very small.

Graceful degradation: privacy vs. moderate coalitions has small cost; vs. majority-colluding, cost grows significantly. Threat model matters for deployment.

$\log_2 10000! \approx 10000 \log_2 10000 - 10000/\ln 2 \approx 1.18 \times 10^5$ bits per permutation. Total (per round): $100 \cdot 1.18 \times 10^5 = 1.18 \times 10^7$ bits = ~1.5 MB.

For a 1 GB file ($8 \times 10^9$ bits): overhead is $1.5 \times 10^6 / 8 \times 10^9 \approx 0.02\%$. Negligible.

For small messages (1 KB), overhead would be 150% — not practical. Privacy scheme is economical only for large-file delivery (media, software updates).

A master key of $k$ bits (e.g., 256-bit AES key) can generate an arbitrarily long pseudorandom permutation via PRF. Computational security; IT privacy guarantee lost but practical security excellent.

Most deployments use hybrid: IT privacy of permutation structure + computational security of actual key bits. Effective privacy is IT-strong as long as PRF is secure.

Theoretical $\log N!$ bits is an upper bound. Practical deployments reduce to a few hundred bits of shared state per user, with security equivalent to underlying PRF.

• Post-quantum threat models.
• Medical / legal / national security content.
• Long-term archival privacy (future quantum computers).
• Any application where "forever secret" matters.

• Routine consumer CDN (email, entertainment).
• Small file sizes (where IT overhead is high).
• Systems with no pre-shared-key infrastructure.

Most practical systems use hybrid: IT-structure + cryptographic key derivation. Get "best of both" with minor operational cost.

Among $K$ users, $z$ collude (coalition $\mathcal{Z}$); $K - z$ are honest. Privacy must hold against $\mathcal{Z}$.

Honest users' demands $\mathbf{d}_{[K] \setminus \mathcal{Z}}$ masked with shared randomness not known to the coalition. Coalition sees masked indices; cannot invert without keys.

MAN delivery on the $K - z$ honest users: rate $(K-z)(1-\mu)/(1+(K-z)\mu)$. Coalition members' own demands are also served (they know their own keys), but their information contribution to coded multicast effectively vanishes vs the honest users (since the coalition's messages leak).

Coalition's collective view $\{X_i, \mathcal{Z}_i, d_i\}_{i \in \mathcal{Z}}$ reveals nothing about $\mathbf{d}_{[K] \setminus \mathcal{Z}}$ — because the honest users' demands are masked by keys the coalition doesn't have. $\blacksquare$

Honest users form a sub-system; MAN converse applies within. Cache + delivery must decode $(K-z)$ files.

Standard MAN converse (Yu-Maddah-Ali-Avestimehr) applied to $K-z$: $R \geq (K-z)(1-\mu)/(1+(K-z)\mu)$ for uncoded placement.

Wan-Caire extended (Exercise 11) matches. $\blacksquare$

Lampiris-Caire beamforming uses knowledge of user channels AND demands. If demands are private, server must precode using masked demands — may lose spatial-multiplexing gain.

Wan-Caire 2023+ results show: spatial DoF $L$ is retained under privacy constraints if the server is trusted. DoF = $t + L$ unchanged. If server is adversarial, spatial gain reduces.

Exact characterization for multi-antenna + privacy + untrusted server is an open question. Chapter 12 focuses on trusted- server case.

Cache privacy: $I(\mathcal{Z}_{-k}; \mathcal{Z}_k, X) = 0$ (user $k$ learns nothing about others' cache contents).

Under random uniform placement, each user already has little information about others' caches — but not zero, since they all share the library.

With random placement + shared randomness for subfile labels, one could achieve $I = 0$. But this would require masking cache contents — potentially at delivery-rate cost.

Cache privacy has not been systematically studied. A research direction for CommIT or similar groups.

Differential privacy: add noise to query responses so output distribution is close (within $\epsilon$) across neighboring inputs. Relaxed notion of privacy.

Exact zero leakage. Stronger than DP.

DP-based coded caching would add noise to demand vector; achieve $(ε, δ)$-privacy. Cost: additional rate/complexity. IT privacy (Wan-Caire) achieves zero leakage at zero rate cost — strictly better.

IT privacy is the "right" framework for coded caching because it can be achieved without rate cost (shared randomness is cheap). DP-based approaches might be useful in alternative architectures where shared keys are expensive.