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

Abstract

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\ge \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\le \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.

arXiv commentSubmitted to IEEE Transactions on Information Theory, February 2017

References in corpus (7)

• Private Information Retrieval from Coded Databases with Colluding Servers
• The Capacity of Robust Private Information Retrieval with Colluding Databases
• The Capacity of Private Information Retrieval
• The Capacity of Symmetric Private Information Retrieval
• Symmetric Private Information Retrieval For MDS Coded Distributed Storage
• Blind Interference Alignment for Private Information Retrieval
• Optimal Download Cost of Private Information Retrieval for Arbitrary Message Length

Cited by in corpus (9)

• Linear Symmetric Private Information Retrieval for MDS Coded Distributed Storage with Colluding Servers
• Private Information Retrieval from MDS Coded Databases with Colluding Servers under Several Variant Models
• A general private information retrieval scheme for MDS coded databases with colluding servers
• Private Information Retrieval from Storage Constrained Databases -- Coded Caching meets PIR
• The Capacity of Private Information Retrieval with Partially Known Private Side Information
• Secure Symmetric Private Information Retrieval from Colluding Databases with Adversaries
• Fundamental Limits of Cache-Aided Private Information Retrieval with Unknown and Uncoded Prefetching
• Cross Subspace Alignment and the Asymptotic Capacity of $X$-Secure $T$-Private Information Retrieval
• The Asymptotic Capacity of Private Search