  Recently it was shown that the seminal Maddah-Ali and Niesen (MAN) coded
caching scheme leaks the demand information of each user to the others. Many
works have considered coded caching with demand privacy, while each non-trivial
existing coded caching scheme with private demands was built on the fact that
the cache information of each user is private to the others. However, most of
these schemes leak the users' cache information. Consequently, in most
realistic settings (e.g., video streaming), where the system is used over time
with multiple sequential transmission rounds, these schemes leak demand privacy
beyond the first round. This observation motivates our new formulation of coded
caching with simultaneously private demands and caches. The main contribution
of this paper is a new construction that generates private coded caching
schemes by leveraging two-server private information retrieval (PIR) schemes.
We show that if in the PIR scheme the demand is uniform over all files and the
queries are independent, the resulting caching scheme is private on both the
demands and on the caches. Interestingly, we propose a new construction of
two-server PIR schemes in this class by leveraging coded caching schemes. By
applying the seminal MAN coded caching scheme into our construction, the
resulting two-server PIR scheme is proved to be order optimal. This is a second
new structural result, somehow closing the loop in the relation between coded
caching and PIR. Finally, to explore a broader tradeoff between cache privacy
and transmission load, we relax the cache privacy constraint and introduce the
definition of leakage on cache information. Then, again as a by-product of our
new construction, we propose new schemes with perfect demand privacy and
imperfect cache privacy that achieve an order-gain in load with respect to the
scheme with perfect privacy on both demands and caches.
