Ferkans — Interactive Telecom Tutor

D2D Privacy Is Harder

The Wan-Caire result (§12.2) holds for shared-link caching — server-to-users broadcast with a single trusted server. In D2D caching (Ch 10), the setting is more delicate: users are themselves transmitters, so privacy-preserving delivery means users must not learn other users' demands from their cached content or from the D2D transmissions they observe.

Moreover, users can collude: $z$ of them could pool their caches and observed messages to infer non-colluding users' demands. The Wan-Sun-Ji-Tuninetti-Caire CommIT result characterizes the fundamental limits of D2D private caching under collusion of any size $z$ .

This section presents the model and main theorem.

Definition:
D2D Private Caching with $z$ -Collusion

A $z$ -private D2D caching scheme ensures that any coalition of $z$ colluding users cannot learn the demands of non-colluding users: $I\!\left(\mathbf{d}_{[K] \setminus \mathcal{Z}};\; \{X_{i}\}_{i \in \mathcal{Z}}, \{\mathcal{Z}_i\}_{i \in \mathcal{Z}}, \{d_i\}_{i \in \mathcal{Z}} \right) \;=\; 0, \quad \forall \mathcal{Z} \subseteq [K], |\mathcal{Z}| \leq z.$ Here $\mathcal{Z}$ is the colluding coalition, and $\{X_i\}_{i \in \mathcal{Z}}$ are the messages received/observed by coalition members.

For $z = 1$ : single-user privacy (Wan-Caire result). For $z = K$ : trivial (everyone knows everything). Interesting regime: moderate $z$ (1-5 users colluding) — the "large adversarial fraction" case.

Theorem: Wan-Sun-Ji-Tuninetti-Caire $z$ -Private Rate

For the D2D private caching problem with $K$ users, $N$ files, per-user cache $M$ , and colluding coalition of size $z$ , the achievable rate under $z$ -privacy is $R_{\text{priv}, z}(M) \;=\; (K - z) \cdot \frac{1 - \mu}{1 + (K - z) \mu}.$ That is, the effective user count reduces from $K$ to $K - z$ . Privacy against $z$ -collusion costs caching gain: the effective group size is smaller, and $t_{\text{eff}} = (K-z) M/N$ replaces the original $t$ .

Each colluding user contributes to the coalition's information. The non-colluding users' demands must be protected against any coalition of size $z$ . By the union-bound-like argument, the effective number of users "helping" the coded multicast reduces by $z$ .

Privacy against the full coalition ( $z = K$ ) is impossible at positive rate — then everyone knows all demands, no privacy guarantee can be provided.

Proof

Reduce to (K-z) users

Any coalition of $z$ users is visible; privacy is guaranteed relative to the remaining $K - z$ . Treat the $K - z$ non-colluding users as a smaller MAN-style problem.

Apply Wan-Caire on $(K - z)$ users

The Wan-Caire scheme extended to D2D achieves rate $(K-z)(1 - \mu)/(1 + (K-z) \mu)$ on the non-colluding population.

Coalition's effect

Colluding users can still receive their own files via D2D — they just don't help in the coded multicast for non-colluding users. Effective $K_{\text{eff}} = K - z$ .

Privacy argument

The coalition's collective cache + observed messages reveals nothing about non-colluding users' demands due to the masking permutations (extended to D2D with user-specific shared randomness). $\blacksquare$

🎓CommIT Contribution(2022)

D2D Private Caching under User Collusion

K. Wan, L. Sun, M. Ji, D. Tuninetti, G. Caire — IEEE Transactions on Information Theory

The Wan-Sun-Ji-Tuninetti-Caire CommIT result extends demand privacy to D2D networks with user collusion. Key contributions:

Coalition model. Characterizes privacy against any coalition of size $z \in [1, K-1]$ .
Achievable rate. Effective $K_{\text{eff}} = K - z$ in the MAN rate formula. Privacy against larger coalitions costs caching gain.
Converse. Shows the $(K-z)$ reduction is tight — no scheme achieves higher rate under $z$ -privacy.
Tradeoff curve. At $z \ll K$ : small privacy cost. At $z \to K$ : privacy vanishes (trivial).

The result characterizes the "price of privacy" in D2D coded caching. For practical $z$ (say 1-5 curious users), the rate penalty is modest; for adversarial settings where half the users might collude, the price is substantial.

coded-cachingprivacycommitd2dcollusionView Paper →

Private Rate vs Colluding Coalition Size

Achievable private rate under $z$ -collusion as a function of $z$ . At $z = 0$ (no collusion): full MAN rate. At $z = K$ : rate 0 (everyone colludes; no privacy possible). Smooth decrease in between.

Parameters

Users K10

Memory ratio μ0.3

Example: Cost of Privacy Against 20% Collusion

For a network of $K = 50$ users, cache ratio $\mu = 0.1$ , allowing up to $z = 10$ (20% of users) to collude: compute the rate penalty vs no collusion.

Solution

No collusion ($z = 0$)

$R_0 = 50 \cdot 0.9/(1 + 5) = 45/6 = 7.5$ files/round.

$z = 10$

$R_{10} = (50 - 10) \cdot 0.9/(1 + 40 \cdot 0.1) = 40 \cdot 0.9/5 = 7.2$ files/round.

Ratio

$R_{10}/R_0 = 7.2/7.5 = 0.96$ . Only 4% rate penalty to protect against 20% collusion — very modest price.

Conclusion

For practical levels of collusion (1-20% of users), the rate penalty is small. The CommIT result says privacy in D2D is nearly free up to substantial adversarial fractions.

Key Takeaway

D2D privacy costs rate proportional to coalition size. Effective users $K_{\text{eff}} = K - z$ . For small $z$ (typical threat model): rate penalty is negligible. For $z \to K$ (all- colluding): rate $\to 0$ . The graceful degradation is a Wan-Sun- Ji-Tuninetti-Caire CommIT result and provides the theoretical justification for privacy-preserving D2D deployments.

Privacy in Cooperative Settings

There is a subtle tension between cooperation (Chapters 5, 9) and privacy (Chapter 12). Cooperation among servers / APs requires them to know user demands to coordinate precoding; this is fundamentally at odds with demand privacy.

Resolution in practice:

Privacy at user level, not server. The server coordinates delivery knowing demands; privacy is enforced against other users. The server is trusted.
Encrypted aggregates. Servers compute precoders from encrypted demand aggregates without learning individual demands. Homomorphic encryption / MPC — expensive in practice.
Distributed randomization. Users inject noise into reported demands; server sees only aggregates. Statistical privacy, weaker than IT privacy.

The CommIT group's work focuses on (1) — server is trusted but other users are adversaries. For pure D2D without any trusted server, (2) or (3) may be needed.

D2D Private Caching and User Collusion