  This paper considers the problem of single-server single-message private
information retrieval with coded side information (PIR-CSI). In this problem,
there is a server storing a database, and a user which knows a linear
combination of a subset of messages in the database as a side information. The
number of messages contributing to the side information is known to the server,
but the indices and the coefficients of these messages are unknown to the
server. The user wishes to download a message from the server privately, i.e.,
without revealing which message it is requesting, while minimizing the download
cost. In this work, we consider two different settings for the PIR-CSI problem
depending on the demanded message being or not being one of the messages
contributing to the side information. For each setting, we prove an upper bound
on the maximum download rate as a function of the size of the database and the
size of the side information, and propose a protocol that achieves the rate
upper-bound.
