Improved Characterization of the Memory-Rate Tradeoff for Demand-Private Coded Caching With Multiple Demands

Abstract

We consider a coded caching problem with multiple demands under a privacy constraint. In this problem, a server with access to $N$ files serves $K$ users over a shared link, and each user requests $L$ distinct files. The privacy constraint requires that each user obtain no information about the demands of the other users. We first propose a new achievable scheme for arbitrary $N$, $K$, and $L$ by applying a novel transformation to a suitable non-private coded caching scheme. We then derive a new converse bound, and show that the proposed scheme is order optimal within a multiplicative factor of $6$ of this bound. Finally, for the case of two users, we completely characterize the optimal memory-rate tradeoff for arbitrary $N$ and $L$ through three new achievable schemes and matching converse bounds.

22 pages, 2 figures. Extended version prepared for journal submission. The conference version was accepted at IEEE GLOBECOM 2026; for the version corresponding to the conference paper, see v2. This version contains substantial new results; the title and author list have been updated