Order-Optimal Coded Caching With File and Demand Privacy
Abstract
We study coded caching with joint file and demand privacy: each user recovers its requested file while learning nothing about the remaining files and the other users' requests jointly. Let N and K be the numbers of files and users, and let M and R denote the cache memory and delivery rate, both normalized by the file size. For every N,K≥2 and every feasible cache size, we give a scheme whose worst-case delivery rate is at most 9/2 times the optimum. To reduce the memory used for file shares, the scheme secret-shares N−1 differences relative to a reference file. Cached masks supply the correction needed to recover the requested file from its difference. For each integer t∈{0,…,K−1}, the scheme achieves M=1+(N−1)t/(K−t) and R=K/(t+1). To lower-bound the delivery rate, we compare the joint cache entropy of user groups under alternative demand vectors, using one fixed user's privacy constraint. Two choices of groups determine the optimal delivery rate up to constants at the scale min{K,1+(N−1)/(M−1)} for M>1. At M=1, the exact optimum is K. A complementary bound on joint broadcast entropy gives the minimum memory for unit delivery rate, 1+(N−1)(K−1), and the exact tradeoff on an interval ending at that memory. All schemes and bounds apply to repeated as well as distinct requests.
Related
- Heterogeneous Demand-Private Coded Caching: Exact Characterization for Two Users and Two Files
- Low-Subpacketization MIMO Coded Caching with Flexible Stream Allocation
- Hotplug Coded Caching: Uncoded versus Row-Wise Coded Placements
- The Exact Memory-Rate Tradeoff for Three-User Secure Coded Caching
- Secure Multi-Access Coded Caching: A Lifting Approach
BibTeX
@misc{fang2026orderoptimal,
title = {{Order-Optimal Coded Caching With File and Demand Privacy}},
author = {Han Fang and Nan Liu and Wei Kang},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.06998},
eprint = {2610.06998},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.06998},
}
RIS
TY - UNPB
TI - Order-Optimal Coded Caching With File and Demand Privacy
AU - Han Fang
AU - Nan Liu
AU - Wei Kang
PY - 2026
DA - 2026/10/04
PB - arXiv
DO - 10.48550/arxiv.2610.06998
UR - https://arxiv.org/abs/2610.06998
AB - We study coded caching with joint file and demand privacy: each user recovers its requested file while learning nothing about the remaining files and the other users' requests jointly. Let N and K be the numbers of files and users, and let M and R denote the cache memory and delivery rate, both normalized by the file size. For every N,K≥2 and every feasible cache size, we give a scheme whose worst-case delivery rate is at most 9/2 times the optimum. To reduce the memory used for file shares, the scheme secret-shares N−1 differences relative to a reference file. Cached masks supply the correction needed to recover the requested file from its difference. For each integer t∈{0,…,K−1}, the scheme achieves M=1+(N−1)t/(K−t) and R=K/(t+1). To lower-bound the delivery rate, we compare the joint cache entropy of user groups under alternative demand vectors, using one fixed user's privacy constraint. Two choices of groups determine the optimal delivery rate up to constants at the scale min{K,1+(N−1)/(M−1)} for M>1. At M=1, the exact optimum is K. A complementary bound on joint broadcast entropy gives the minimum memory for unit delivery rate, 1+(N−1)(K−1), and the exact tradeoff on an interval ending at that memory. All schemes and bounds apply to repeated as well as distinct requests.
ER -