Abstract
We investigate the demand private coded caching problem, which is an $(N,K)$ coded caching problem with $N$ files, $K$ users, each equipped with a cache of size $M$, and an additional privacy constraint on user demands. We first present a new virtual-user-based achievable scheme for arbitrary number of users and files. Then, for the case of 2 files and arbitrary number of users, we derive some new converse bounds. As a result, we obtain the exact memory-rate tradeoff of the demand private coded caching problem for 2 files and 3 users. As for the case of 2 files and arbitrary number of users, the exact memory-rate tradeoff is characterized for $M\in [0,\frac{2}{K}] \cup [\frac{2(K-1)}{K+1},2]$.
Introduction
In standard coded caching, a central server delivers content to multiple users over a shared link. By leveraging local caches and broadcasting XORed combinations of files, the server can significantly reduce bandwidth. However, this efficiency comes at a cost: privacy. In a typical broadcast, a user can often infer the requests of their neighbors by observing the transmitted signals and comparing them with their own cache contents.
This paper addresses Demand Private Coded Caching, where a strict privacy constraint is enforced: no user should gain any information about the files requested by others. The goal is to determine the optimal memory-rate tradeoff—the minimum broadcast rate ($R$) needed for a given cache size ($M$) while maintaining perfect privacy.
The Virtual-User Achievable Scheme
The authors introduce a novel achievable scheme based on the concept of "virtual users." To mask a user's actual demand, the server simulates a scenario with $NK$ virtual requests. By ensuring that every file in the library is requested an equal number of times across these virtual instances, the server creates a symmetric broadcast signal. This symmetry makes the specific file requested by any individual user indistinguishable from the "noise" of the other virtual deliveries.
As shown in the mapping vectors above, the scheme relies on structured request patterns to maintain privacy. The delivery phase then uses these patterns to generate transmission signals. This approach effectively "swaps" the roles of cache size and delivery rate parameters from previous non-private schemes, allowing the authors to adapt efficient techniques like the Yu-Maddah-Ali (YMA) scheme to a private context.
Theoretical Insights and Converse Bounds
Beyond constructive schemes, the paper provides rigorous information-theoretic proofs to establish lower bounds (converse bounds). For the specific case of a two-file library ($N=2$), the authors utilize the submodularity of entropy and recursive induction to bound the joint entropy of cache contents and delivery signals.
A key insight is that privacy is achieved through "over-delivery." The server must send extra information to satisfy a set of requests that covers all possibilities, thereby buying privacy at the cost of a higher transmission rate compared to non-private caching. This trade-off is particularly advantageous when user caches are small ($M$ is low) and the number of users exceeds the number of files ($N \leq K$).
Key Results
The research yields several significant characterizations of the memory-rate tradeoff, supported by numerical comparisons against existing benchmarks like the Gurjarpadhye et al. scheme:
- Exact Tradeoff for (2, 3): The authors successfully characterize the exact optimal tradeoff for the 2-file, 3-user scenario. The resulting curve is piecewise linear, defined by critical points such as $(2/3, 1)$ and $(1, 2/3)$.
- Partial Characterization for (2, K): For 2 files and an arbitrary number of users $K$, the exact tradeoff is determined for very small caches ($M \in [0, 2/K]$) and very large caches ($M \in [2(K-1)/(K+1), 2]$).
- General Upper Bound: Theorem 1 in the paper provides a new general formula for the $(M, R)$ pair applicable to any number of files and users, setting a new benchmark for the general problem.
Conclusion and Future Directions
While this work makes significant strides in characterizing the two-file case, challenges remain. For $K > 3$ users, there is still a "middle" range of cache sizes where the exact optimal rate is unknown. Furthermore, extending the tight recursive entropy proofs to libraries with more than two files ($N > 2$) remains a major open problem. Future research may also investigate whether "coded placement" could further optimize the memory-rate tradeoff.
Summary updated