Chapter Summary

Chapter Summary

Key Points

• 1.

  Information-theoretic demand privacy requires that each user learns zero information about other users' demands from its received messages and cache. Formally: $I(\mathbf{d}_{-k}; X, \mathcal{Z}_k | d_k) = 0$. Stronger than cryptographic privacy.

• 2.

  The standard MAN scheme leaks. In MAN delivery, users must know all demands to XOR-decode. Leakage is $O(K \log N)$ bits per round — substantial.

• 3.

  Wan-Caire 2021 (CommIT): Demand privacy in shared-link coded caching is free. The MAN rate $R = K(1-M/N)/(1+KM/N)$ is achievable with zero leakage via shared randomness (per-user secret permutations).

• 4.

  Wan-Sun-Ji-Tuninetti-Caire 2022 (CommIT): In D2D private caching with coalitions of size $z$, the achievable rate is $(K-z)(1-\mu)/(1 + (K-z)\mu)$. Effective users reduce from $K$ to $K-z$. For small $z$, rate penalty is small.

• 5.

  Shared randomness is the key tool. Pre-distributed permutations (via PKI, Diffie-Hellman, or SIM) enable the server to mask demands so users can decode their own files without inferring others'.

• 6.

  Collusion tradeoff. Privacy against larger coalitions costs more rate. For $z \sim K$ (everyone colludes), no privacy is possible. For $z \ll K$ (typical threat model), cost is small.

• 7.

  Engineering reality. Shared-randomness overhead is negligible for large files (~MB) but non-trivial for small messages. SIM-based pre-shared keys in 5G provide a natural infrastructure for deployment.