Converse for Symmetric Multi-Server Single-Message PIR with Side Information
Li Su, Michael Gastpar · arXiv (Cornell University) · 2018
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. For all coding schemes satisfying a symmetry condition, we prove a converse for multi-server single-message PIR with side information. Specifically, in this case, it is shown that the capacity is $(1+\frac{1}{N}+\frac{1}{N^2}+\dots+\frac{1}{N^{\left\lceil \frac{K}{M+1}\right\rceil-1}})^{-1}$.