  We study the role of coded side information in single-server Private
Information Retrieval (PIR). An instance of the single-server PIR problem
includes a server that stores a database of $K$ independently and uniformly
distributed messages, and a user who wants to retrieve one of these messages
from the server. We consider settings in which the user initially has access to
a coded side information which includes a linear combination of a subset of $M$
messages in the database. We assume that the identities of the $M$ messages
that form the support set of the coded side information as well as the coding
coefficients are initially unknown to the server. We consider two different
models, depending on whether the support set of the coded side information
includes the requested message or not. We also consider the following two
privacy requirements: (i) the identities of both the demand and the support set
of the coded side information need to be protected, or (ii) only the identity
of the demand needs to be protected. For each model and for each of the privacy
requirements, we consider the problem of designing a protocol for generating
the user's query and the server's answer that enables the user to decode the
message they need while satisfying the privacy requirement. We characterize the
(scalar-linear) capacity of each setting, defined as the ratio of the number of
information bits in a message to the minimum number of information bits
downloaded from the server over all (scalar-linear) protocols that satisfy the
privacy condition. Our converse proofs rely on new information-theoretic
arguments---tailored to the setting of single-server PIR and different from the
commonly-used techniques in multi-server PIR settings. We also present novel
capacity-achieving scalar-linear protocols for each of the settings being
considered.
