The Capacity of Private Information Retrieval with Partially Known Private Side Information

Abstract

We consider the problem of private information retrieval (PIR) of a single message out of $K$ messages from $N$ replicated and non-colluding databases where a cache-enabled user (retriever) of cache-size $M$ possesses side information in the form of full messages that are partially known to the databases. In this model, the user and the databases engage in a two-phase scheme, namely, the prefetching phase where the user acquires side information and the retrieval phase where the user downloads desired information. In the prefetching phase, the user receives $m_n$ full messages from the $n$th database, under the cache memory size constraint ${\sum }_{n=1}^N{m}_n\le M$. In the retrieval phase, the user wishes to retrieve a message such that no individual database learns anything about the identity of the desired message. In addition, the identities of the side information messages that the user did not prefetch from a database must remain private against that database. Since the side information provided by each database in the prefetching phase is known by the providing database and the side information must be kept private against the remaining databases, we coin this model as \textit{partially known private side information}. We characterize the capacity of the PIR with partially known private side information to be $C={\left(1+\frac{1}{N}+\cdots +\frac{1}{N^{K-M-1}}\right)}^{-1}=\frac{1-\frac{1}{N}}{1-(\frac{1}{N}{)}^{K-M}}$. Interestingly, this result is the same if none of the databases knows any of the prefetched side information, i.e., when the side information is obtained externally, a problem posed by Kadhe et al. and settled by Chen-Wang-Jafar recently. Thus, our result implies that there is no loss in using the same databases for both prefetching and retrieval phases.

arXiv commentSubmitted to IEEE Transactions on Information Theory, November 2017

References in corpus (15)

• Private Information Retrieval from Coded Databases with Colluding Servers
• Linear Symmetric Private Information Retrieval for MDS Coded Distributed Storage with Colluding Servers
• The Capacity of Robust Private Information Retrieval with Colluding Databases
• A general private information retrieval scheme for MDS coded databases with colluding servers
• Private Information Retrieval Schemes for Coded Data with Arbitrary Collusion Patterns
• The Capacity of Symmetric Private Information Retrieval
• The Capacity of $T$-Private Information Retrieval with Private Side Information
• Multiround Private Information Retrieval: Capacity and Storage Overhead
• Symmetric Private Information Retrieval For MDS Coded Distributed Storage
• Multi-Message Private Information Retrieval: Capacity Results and Near-Optimal Schemes
• Secure Symmetric Private Information Retrieval from Colluding Databases with Adversaries
• Fundamental Limits of Cache-Aided Private Information Retrieval with Unknown and Uncoded Prefetching
• Blind Interference Alignment for Private Information Retrieval
• Optimal Download Cost of Private Information Retrieval for Arbitrary Message Length
• Preserving Privacy while Broadcasting: $k$-Limited-Access Schemes

Cited by in corpus (5)

• Private Information Retrieval from MDS Coded Databases with Colluding Servers under Several Variant Models
• Cross Subspace Alignment and the Asymptotic Capacity of $X$-Secure $T$-Private Information Retrieval
• On the Storage Cost of Private Information Retrieval
• The Capacity of Private Information Retrieval with Private Side Information Under Storage Constraints
• Cache-Aided Private Information Retrieval with Partially Known Uncoded Prefetching: Fundamental Limits