The Capacity of Private Information Retrieval with Private Side Information Under Storage Constraints

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 $S$ possesses side information in the form of uncoded portions of the messages that are unknown to the databases. The identities of these side information messages need to be kept private from the databases, i.e., we consider PIR with private side information (PSI). We characterize the optimal normalized download cost for this PIR-PSI problem under the storage constraint $S$ as $D^{\ast }=1+\frac{1}{N}+\frac{1}{N^2}+\cdots +\frac{1}{N^{K-1-M}}+\frac{1-r_M}{N^{K-M}}+\frac{1-r_{M-1}}{N^{K-M+1}}+\cdots +\frac{1-r_1}{N^{K-1}}$, where $r_i$ is the portion of the $i$th side information message that is cached with ${\sum }_{i=1}^M{r}_i=S$. Based on this capacity result, we prove two facts: First, for a fixed memory size $S$ and a fixed number of accessible messages $M$, uniform caching achieves the lowest normalized download cost, i.e., $r_i=\frac{S}{M}$, for $i=1,\dots ,M$, is optimum. Second, for a fixed memory size $S$, among all possible $K-\lceil S\rceil +1$ uniform caching schemes, the uniform caching scheme which caches $M=K$ messages achieves the lowest normalized download cost.

arXiv commentSubmitted for publication, June 2018

References in corpus (14)

• Private Information Retrieval from Coded Databases with Colluding Servers
• Linear Symmetric Private Information Retrieval for MDS Coded Distributed Storage with Colluding Servers
• A general private information retrieval scheme for MDS coded databases with colluding servers
• Private Information Retrieval from Storage Constrained Databases -- Coded Caching meets PIR
• Private Information Retrieval Schemes for Coded Data with Arbitrary Collusion Patterns
• The Capacity of Private Computation
• The Capacity of Private Information Retrieval
• The Capacity of Symmetric Private Information Retrieval
• The Capacity of Private Information Retrieval with Partially Known Private Side Information
• The Capacity of $T$-Private Information Retrieval with Private Side Information
• Symmetric Private Information Retrieval For MDS Coded Distributed Storage
• Secure Symmetric Private Information Retrieval from Colluding Databases with Adversaries
• Fundamental Limits of Cache-Aided Private Information Retrieval with Unknown and Uncoded Prefetching
• The Asymptotic Capacity of Private Search