Converse for Multi-Server Single-Message PIR with Side Information
Li Su, Michael Gastpar
Abstract
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. We prove a converse bound on the maximum download rates, which coincides with the known achievability scheme proposed by Kadhe et. al.. Hence, we characterize the capacity for this problem, which is${\left( {1 + \frac{1}{N} + \frac{1}{{{N^2}}} + \cdots + \frac{1}{{N\left\lceil {\frac{K}{{M + 1}}} \right\rceil - 1}}} \right)^{ - 1}}$. The proof leverages a novel concept that we call virtual side information, which, for a fixed query and any message, identifies the side information that would be needed in order to recover that message.