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 CsP is the maximum number of desired message symbols that can be retrieved privately per downloaded symbol, where the symbols are defined over the same field. For the case P ≥ M/2, we determine the exact sum capacity of MPIR as CPs= 1/(1+(M - P)/(PN)). The achievable scheme in this case is based on downloading MDS-coded mixtures of all messages. For P ≤ 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., M/P ∈ N. In this case, CsP= (1+1/N+⋯+1/NM/P-1)-1, i.e., CsP= (1 - 1/N)/(1 - 1/NM/P) for N>1, and CsP= P/M for N = 1. The achievable scheme in this case generalizes the singlemessage 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 even after considering the free savings that result from downloading undesired symbols in each single-message retrieval round.