Capacity of Single-Server Single-Message Private Information Retrieval with Coded Side Information

Understand

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.