Multi-Message Private Information Retrieval: Capacity Results and Near-Optimal Schemes

We consider the problem of multi-message private information retrieval (MPIR) from $N$ non-communicating replicated databases. In MPIR, the user is interested in retrieving $P$ messages out of $M$ stored messages without leaking the identity of the retrieved messages. The information-theoretic sum capacity of MPIR $C_s^P$ is the maximum number of desired message symbols that can be retrieved privately per downloaded symbol. For the case $P \geq \frac{M}{2}$, we determine the exact sum capacity of MPIR as $C_s^P=\frac{1}{1+\frac{M-P}{PN}}$. The achievable scheme in this case is based on downloading MDS-coded mixtures of all messages. For $P \leq \frac{M}{2}$, we develop lower and upper bounds for all $M,P,N$. These bounds match if the total number of messages $M$ is an integer multiple of the number of desired messages $P$, i.e., $\frac{M}{P} \in \mathbb{N}$. In this case, $C_s^P=\frac{1-\frac{1}{N}}{1-(\frac{1}{N})^{M/P}}$. The achievable scheme in this case generalizes the single-message capacity achieving scheme to have unbalanced number of stages per round of download. For all the remaining cases, the difference between the lower and upper bound is at most $0.0082$, which occurs for $M=5$, $P=2$, $N=2$. Our results indicate that joint retrieval of desired messages is more efficient than successive use of single-message retrieval schemes.