On the Capacity of Single-Server Multi-Message Private Information Retrieval with Side Information

Understand

We study Private Information Retrieval with Side Information (PIR-SI) in the single-server multi-message setting.

• In this setting, a user wants to download $D$ messages from a database of $K\geq D$ messages, stored on a single server, without revealing any information about the identities of the demanded messages to the server.
• The goal of the user is to achieve information-theoretic privacy by leveraging the side information about the database.
• The side information consists of a random subset of $M$ messages in the database which could have been obtained in advance from other users or from previous interactions with the server.