Private Information Retrieval with Side Information

Understand

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.