Demand Private Coded Caching: The Two-File Case

We investigate the demand private coded caching problem, which is an <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$(N,\ K)$</tex> coded caching problem with <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$N$</tex> files, <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$K$</tex> users, each equipped with a cache of size <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$M$</tex>, 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 memoryrate tradeoff is characterized for <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$M\in[0,\ \frac{2}{K}]\cup[\frac{2(K-1)}{K+1},\ 2]$</tex>.