Multi-message private information retrieval

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 CP is the maximum number of desired message symbols that can be retrieved privately per downloaded symbol. For the case P ≥ M/2, we determine the exact sum capacity of MPIR as C
^P
_s
=1/1+M-P/PN For P≤M/2, we develop lower and upper bounds for all M, P, N. These bounds match if the number of messages M is an integer multiple of the number of desired messages P, in which case, C
^P
_s
= 1-1N/1-(1/N)
^M/P
. Our results indicate that joint retrieval of desired messages is more efficient than successive use of single-message retrieval schemes.