Ferkans — Interactive Telecom Tutor

Two Security Questions for Coded Caching

Chapter 12 addressed demand privacy: users should not learn each other's demands. This chapter addresses a complementary question: delivery secrecy. An external eavesdropper $\mathcal{E}$ overhears the broadcast transmission $X$ . Can we design a coded-caching scheme such that $\mathcal{E}$ learns nothing about the file library?

These are two different threat models:

Demand privacy (Ch 12): Internal users are the adversary — each user must not learn other demands.
Delivery secrecy (Ch 17): External eavesdropper is the adversary — must not learn any file content from the broadcast.

Both are relevant in practice: privacy for user protection in shared-link services; secrecy for untrusted networks (wireless broadcast where the medium is open).

Definition:
Secure Delivery Model

The secure coded-caching model (Sengupta-Tandon-Clancy 2015) consists of:

A server with library $\mathcal{W} = \{W_1, \ldots, W_N\}$ .
Users $1, \ldots, K$ with caches $\mathcal{Z}_1, \ldots, \mathcal{Z}_K$ of size $MF$ bits each.
An external eavesdropper $\mathcal{E}$ observing the full broadcast $X$ .

Security requirement: for any demand vector $\mathbf{d}$ , $I(\mathcal{W}; X) \;=\; 0$ (perfect information-theoretic secrecy of the library).

Correctness: each legitimate user $k$ can decode $W_{d_k}$ from its cache $\mathcal{Z}_k$ and the broadcast $X$ .

The eavesdropper sees only $X$ , not the caches. The caches are pre-distributed privately during off-peak (e.g., via physical storage, secure link, or asymmetric keying). The broadcast phase is the only attack surface.

Theorem: Secrecy Requires $M \geq 1$

For perfect-secrecy coded caching with $K$ users, $N \geq K$ files, and cache size $M$ per user, a necessary condition is $M \geq 1$ . No secure scheme exists with $M < 1$ .

The eavesdropper observes $X$ . By the cut-set bound, to decode each file $W_n$ a user needs the sum $M + R \geq 1$ file (bits of info). For secrecy, $X$ must be independent of $\mathcal{W}$ , so $X$ carries "zero information" — all information must come from the cache. Hence $M \geq 1$ .

Proof

Cut-set setup

User $k$ decodes $W_{d_k}$ from $(\mathcal{Z}_k, X)$ . By Fano: $H(W_{d_k} | \mathcal{Z}_k, X) \leq \epsilon F$ for some small $\epsilon$ .

Secrecy condition

Perfect secrecy: $I(\mathcal{W}; X) = 0$ $\Rightarrow$ $I(W_{d_k}; X) = 0$ $\Rightarrow$ $H(W_{d_k} | X) = H(W_{d_k}) = F$ .

Combining

$F - \epsilon F \leq I(W_{d_k}; \mathcal{Z}_k | X) \leq H(\mathcal{Z}_k) = MF$ .

Conclusion

$M \geq 1 - \epsilon$ , so $M \geq 1$ as $\epsilon \to 0$ . The cache must store at least one full file's worth of random key material. $\blacksquare$

Why $M \geq 1$ : Intuition

Think of the cache as a one-time pad store. To decode a requested file $W_{d_k}$ securely, the user needs enough key material to "unmask" the transmission. A one-time pad requires key length = message length = 1 file. Hence $M \geq 1$ .

Coded caching's multicasting gain still applies above the $M \geq 1$ floor: extra memory $M - 1$ provides the MAN rate reduction. So effectively, $M_\text{eff} = M - 1$ replaces $M$ in the rate formula.

Secrecy-Rate-Memory Tradeoff

Secure rate (STC 2015) shifts the MAN curve by 1 file in memory ( $M \to M - 1$ ). At $M = 1$ : secure rate = uncoded MAN. Below $M = 1$ : no secure scheme. Plot both curves for comparison.

Parameters

Users K10

Files N20

Example: Wireless Eavesdropper Scenario

A CDN operator streams video over a wireless broadcast link to $K = 5$ users. An eavesdropper in range also receives the signal. $N = 10$ videos, $M = 1.5$ per user. Quantify security margin.

Solution

Feasibility check

$M = 1.5 \geq 1$ — secure scheme exists.

Effective memory

$M_\text{eff} = M - 1 = 0.5$ . Effective ratio $\mu_\text{eff} = 0.5/10 = 0.05$ .

Secure rate

$R_\text{sec} = K (1 - 0.05)/(1 + K \cdot 0.05) = 5 \cdot 0.95/1.25 = 3.8$ files/channel-use.

Non-secure MAN baseline

$R_\text{MAN} = 5 (1 - 0.15)/(1 + 5 \cdot 0.15) = 5 \cdot 0.85/1.75 = 2.43$ .

Penalty

Secure rate ( $3.8$ ) is worse than non-secure MAN ( $2.43$ ): secure delivery costs $(R_\text{sec} - R_\text{MAN})$ files per use. The 1-file cache is spent on key material.

Leakage

Eavesdropper: $I(\mathcal{W}; X) = 0$ by construction. Perfect secrecy achieved at cost of increased rate.

Common Mistake: Don't Conflate Privacy and Secrecy

Mistake:

Assuming demand-privacy schemes (Wan-Caire, Ch 12) also provide secrecy against external eavesdroppers.

Correction:

Demand privacy masks which file each user wants from other users. The broadcast $X$ itself may still leak file content to an outsider.
Delivery secrecy prevents $\mathcal{E}$ from learning file content. Does not address which file a particular user requested (that's privacy).

In many scenarios you want both. Joint schemes exist (STC 2015 + Wan-Caire masking), but each primitive addresses only one threat.

Key Takeaway

Secure delivery requires at least 1 file of cache per user. This is the fundamental one-time-pad cost of information-theoretic secrecy. Above this floor, coded caching's MAN gain still applies to the remaining memory $M - 1$ . Secrecy is not free — unlike Wan-Caire demand privacy, it costs capacity.

Security Model: Eavesdropper on the Broadcast