  We study the problem of Private Information Retrieval (PIR) in the presence
of prior side information. The problem setup includes a database of $K$
independent messages possibly replicated on several servers, and a user that
needs to retrieve one of these messages. In addition, the user has some prior
side information in the form of a subset of $M$ messages, not containing the
desired message and unknown to the servers. This problem is motivated by
practical settings in which the user can obtain side information
opportunistically from other users or has previously downloaded some messages
using classical PIR schemes. The objective of the user is to retrieve the
required message without revealing its identity while minimizing the amount of
data downloaded from the servers.
  We focus on achieving information-theoretic privacy in two scenarios: (i) the
user wants to protect jointly its demand and side information; (ii) the user
wants to protect only the information about its demand, but not the side
information. To highlight the role of side information, we focus first on the
case of a single server (single database). In the first scenario, we prove that
the minimum download cost is $K-M$ messages, and in the second scenario it is
$\lceil \frac{K}{M+1}\rceil$ messages, which should be compared to $K$
messages, the minimum download cost in the case of no side information. Then,
we extend some of our results to the case of the database replicated on
multiple servers. Our proof techniques relate PIR with side information to the
index coding problem. We leverage this connection to prove converse results, as
well as to design achievability schemes.
