Ferkans — Interactive Telecom Tutor

Privacy Without Rate Cost

The Wan-Caire 2021 CommIT result is striking: demand privacy can be achieved at the same rate as the non-private MAN scheme. Privacy is "free" — the caching gain $(1 + t)$ is retained. This contrasts with classical Shannon secrecy, where private communication costs extra capacity.

The key insight: shared randomness, which is free in the placement phase, is the secret weapon. By pre-distributing key bits, the server can mask delivery messages so users cannot distinguish demands from noise.

This section presents the scheme and the main theorem.

Theorem: Wan-Caire: Private Coded Caching Achieves MAN Rate

For the shared-link coded caching problem with $K$ users, $N$ files, and per-user cache $M$ , demand privacy (as defined in §12.1) is achievable at delivery rate $R_{\text{priv}} \;=\; K \cdot \frac{1 - \mu}{1 + K \mu},$ matching the non-private MAN rate, provided the users share randomness of $O(\log N)$ bits per delivery round.

The scheme extends MAN: users cache the same combinatorial pattern. In delivery, the server permutes the file indices using shared randomness, so users cannot identify which summand corresponds to which file. Each user decodes its own demand using knowledge of the permutation, but learns nothing about other users' demands. Rate unchanged; privacy gained.

Proof

Placement

Standard MAN placement: each file $W_n$ split into $\binom{K}{t}$ subfiles; user $k$ caches $W_{n, \mathcal{S}}$ iff $k \in \mathcal{S}$ .

Shared randomness setup

Pre-distribute $K$ random permutations $\pi_1, \ldots, \pi_K$ over $[N]$ , one per user. Only user $k$ knows $\pi_k$ . Each $\pi_k$ uses $\log_2 N!$ bits — a small constant per user.

Demand masking

User $k$ sends its demand to the server masked: $\tilde{d}_k = \pi_k(d_k)$ . Server receives $\tilde{\mathbf{d}} = (\tilde d_1, \ldots, \tilde d_K)$ and cannot determine $\mathbf{d}$ (each $\pi_k$ is a user-specific random permutation).

Delivery

Server runs standard MAN delivery on masked demands $\tilde{\mathbf{d}}$ : broadcast XOR messages $X_{\mathcal{S}'} = \bigoplus_{k \in \mathcal{S}'} W_{\tilde d_k, \mathcal{S}' \setminus \{k\}}$ .

User decoding

User $k$ knows $\pi_k$ and $d_k$ , so recovers $\tilde d_k = \pi_k(d_k)$ . It then XOR-cancels using cached subfiles whose labels are $\tilde d_j$ — which user $k$ does not know without $\pi_j$ . Instead, user $k$ cancels using all cached subfiles indexed by $\mathcal{S}' \setminus \{k\}$ ; the structure of MAN ensures only the desired subfile survives.

Privacy

User $k$ sees masked indices $\tilde{\mathbf{d}}_{-k}$ but does not know $\pi_{-k}$ , so $\tilde d_j$ reveals nothing about $d_j$ for $j \neq k$ (uniform random permutation). $I(\mathbf{d}_{-k}; X, \mathcal{Z}_k, d_k) = 0$ . $\blacksquare$

🎓CommIT Contribution(2021)

Demand-Private Coded Caching at MAN Rate

K. Wan, G. Caire — IEEE Transactions on Information Theory

Wan and Caire established that demand privacy in coded caching is free in the information-theoretic sense: the non-private MAN rate $R = K(1 - M/N)/(1 + KM/N)$ is achievable under strict information-theoretic privacy (zero mutual information between a user's observations and other users' demands).

Key ideas.

Shared randomness masks demands. Each user holds a secret permutation $\pi_k$ over the library. Demands are reported in masked form; only user $k$ can invert $\pi_k$ .
MAN delivery on masked demands. The server runs standard MAN with the masked demand vector; the XOR structure is unchanged.
Perfect privacy. Users decode their own files using their own key; cannot decode others' files nor infer their demands.

The scheme shows privacy and rate are not in tension for coded caching — a remarkably positive result for a security-conscious design. CommIT follow-up work extends this to the D2D setting (§12.3) and mixed-traffic cases.

coded-cachingprivacycommitView Paper →

Wan-Caire Demand-Privacy Scheme

The server holds the library

\mathcal{W}

. Each user has its own cache

\mathcal{Z}_k

and a secret permutation

\pi_k

(shared key). Users send masked demands

\tilde{d}_k = \pi_k(d_k)

; the server runs MAN delivery on masked demands. Each user decodes its own file; learns zero information about others'. The rate equals the non-private MAN rate:

R = K(1-M/N)/(1+KM/N)

.

Private vs Non-Private Rate Curves

The Wan-Caire private rate matches MAN exactly: two curves overlap across all memory ratios. Uncoded private (no MAN gain) baseline shown for contrast — loses the coded-caching gain.

Parameters

Users K10

Files N10

Demand Leakage: Private vs Non-Private

Mutual-information leakage of user $k$ about $\mathbf{d}_{-k}$ . Non-private MAN: $O(K \log N)$ bits — linear in users. Wan-Caire private: exactly 0 by construction. Gap is enormous even for modest $K$ .

Parameters

Max K50

Example: Wan-Caire Scheme Walkthrough

For $K = 3$ , $N = 4$ , $M = 4/3$ (integer $t = KM/N = 1$ ), walk through the Wan-Caire private scheme for demands $d_1 = 1, d_2 = 2, d_3 = 3$ .

Solution

Placement

MAN with $t = 1$ : each file split into $\binom{3}{1} = 3$ subfiles. User $k$ caches $W_{n, \{k\}}$ for all $n \in [4]$ .

Setup randomness

Each user has a private permutation $\pi_k$ of $[4]$ . Suppose $\pi_1 = (2,3,4,1)$ , $\pi_2 = (4,1,2,3)$ , $\pi_3 = (3,4,1,2)$ .

Mask demands

$\tilde d_1 = \pi_1(1) = 2$ . $\tilde d_2 = \pi_2(2) = 1$ . $\tilde d_3 = \pi_3(3) = 1$ . So $\tilde{\mathbf{d}} = (2, 1, 1)$ .

Server delivery

For $\mathcal{S}' = \{1,2,3\}$ , XOR message: $X = W_{2, \{2,3\}} \oplus W_{1, \{1,3\}} \oplus W_{1, \{1,2\}}$ . Wait — $\tilde d_2 = \tilde d_3 = 1$ , so 2 of 3 summands involve $W_1$ . The MAN machinery still works: server transmits this XOR.

User 1 decodes

User 1 knows $\pi_1$ , so knows $\tilde d_1 = 2$ . Its missing subfile of $W_2$ is $W_{2, \{2,3\}}$ . Cancel using cached $W_{1, \{1,3\}}, W_{1, \{1,2\}}$ . (Both indexed by sets containing 1.) Recover $W_{2, \{2,3\}}$ , reconstruct $W_2$ .

Note: user 1 doesn't know $\pi_2, \pi_3$ , so doesn't know that $\tilde d_2 = 1$ corresponds to $d_2 = 2$ . Hence privacy preserved.

Verify rate

Same rate as MAN: 1 XOR of $F/3$ bits per delivery, 1 message per $(t+1)$ -subset. Rate = $1/3$ file per channel use (at $t = 1$ , $K=3$ : $R = (3-1)/2 = 1$ file). Match.

Common Mistake: Wan-Caire Assumes Uniform Demand Prior

Mistake:

Applying Wan-Caire's zero-leakage result when user demands are not uniformly distributed.

Correction:

The scheme achieves $I(\mathbf{d}_{-k}; X | \mathcal{Z}_k, d_k) = 0$ under the assumption that demands are i.i.d. uniform over $[N]$ . For non-uniform (e.g., Zipf) demands, the leakage is reduced but not zero: the scheme reveals some bias through the permutation's statistics.

Practical deployments may need stronger randomness (larger key space) for non-uniform demands, or additional noise (differential privacy techniques). The scaling-law rate is still preserved; only the exact zero-leakage guarantee degrades.

Why Privacy Is Free

At first glance it seems surprising that privacy costs nothing. The reason, in information-theoretic terms:

MAN uses symmetric delivery structure. Every XOR message has the same combinatorial form, indexed by $(t+1)$ -subsets. The structural "shape" of delivery doesn't depend on demands.
Only labels leak. The file indices $d_k$ within the summands carry demand information, not the XOR structure itself. Masking the labels via permutation (one per user) hides this while preserving the XOR's combinatorial utility.
No rate penalty. The permutation is applied at the label layer, not the XOR payload. The payload's bit-count is unchanged.

The result: full MAN rate + full privacy. A rare win-win.

Wan-Caire: Private Coded Caching at MAN Rate

Privacy Without Rate Cost

Theorem: Wan-Caire: Private Coded Caching Achieves MAN Rate

Placement

Shared randomness setup

Demand masking

Delivery

User decoding

Privacy

Demand-Private Coded Caching at MAN Rate

Wan-Caire Demand-Privacy Scheme

Private vs Non-Private Rate Curves

Parameters

Demand Leakage: Private vs Non-Private

Parameters

Example: Wan-Caire Scheme Walkthrough

Placement

Setup randomness

Mask demands

Server delivery

User 1 decodes

Verify rate

Common Mistake: Wan-Caire Assumes Uniform Demand Prior

Why Privacy Is Free