  Caching is an efficient way to reduce network traffic congestion during peak
hours by storing some content at the user's local cache memory without
knowledge of later demands. For the shared-link caching model, Maddah-Ali and
Niesen (MAN) proposed a two-phase (placement and delivery) coded caching
strategy, which is order optimal within a constant factor. However, in the MAN
coded caching scheme, each user can obtain the information about the demands of
other users, i.e., the MAN coded caching scheme is inherently prone to
tampering and spying the activity/demands of other users. In this paper, we
formulate an information-theoretic shared-link caching model with private
demands, where there are K cache-aided users (which can cache up to M files)
connected to a central server with access to N files. Each user requests L
files. Our objective is to design a two-phase private caching scheme with
minimum load while preserving the information-theoretic privacy of the demands
of each user with respect to other users.
  We propose two novel private coded caching schemes with the general
underlying idea, which is to satisfy the users' requests by generating a set of
coded multicast messages that is symmetric with respect to the library files.
In the first scheme, we introduce a number of virtual users such that each
L-subset of files is demanded by K real or virtual (effective) users and use
the MAN delivery to generate multicast messages. This scheme incurs in an
extremely large sub-packetization. Then, we propose a second scheme based on a
novel MDS-coded cache placement. In this case, we generate multicast messages
where each multicast message contains one MDS-coded symbol from each file in
the library and thus is again symmetric over all the files from the viewpoint
of each user. The proposed schemes are generally order optimal except for the
case where N > LK and M< N/K.
