Converse for Multi-Server Single-Message PIR with Side Information

Understand

Multi-server single-message private information retrieval is studied in the presence of side information.

• In this problem, $K$ independent messages are replicatively stored at $N$ non-colluding servers.
• The user wants to privately download one message from the servers without revealing the index of the message to any of the servers, leveraging its $M$ side information messages.
• We assume that the servers only know the number of the side information messages available at the user but not their indices.