Cache-Aided Private Information Retrieval with Partially Known Uncoded Prefetching: Fundamental Limits

Abstract

We consider the problem of private information retrieval (PIR) from $N$ non-colluding and replicated databases, when the user is equipped with a cache that holds an uncoded fraction $r$ of the symbols from each of the $K$ stored messages in the databases. This model operates in a two-phase scheme, namely, the prefetching phase where the user acquires side information and the retrieval phase where the user privately downloads the desired message. In the prefetching phase, the user receives $\frac{r}{N}$ uncoded fraction of each message from the $n$th database. This side information is known only to the $n$th database and unknown to the remaining databases, i.e., the user possesses \emph{partially known} side information. We investigate the optimal normalized download cost $D^{\ast }(r)$ in the retrieval phase as a function of $K$, $N$, $r$. We develop lower and upper bounds for the optimal download cost. The bounds match in general for the cases of very low caching ratio ($r\le \frac{1}{N^{K-1}}$) and very high caching ratio ($r\ge \frac{K-2}{N^2-3N+KN}$). We fully characterize the optimal download cost caching ratio tradeoff for $K=3$. For general $K$, $N$, and $r$, we show that the largest gap between the achievability and the converse bounds is $\frac{5}{32}$.

Submitted for publication, December 2017. arXiv admin note: substantial text overlap with arXiv:1709.01056

References in corpus (20)

• Private Information Retrieval from Coded Databases with Colluding Servers
• Wireless Content Caching for Small Cell and D2D Networks
• Fundamental Limits of Caching with Secure Delivery
• 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 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 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
• Multiround Private Information Retrieval: Capacity and Storage Overhead
• Symmetric Private Information Retrieval For MDS Coded Distributed Storage
• Secure Symmetric Private Information Retrieval from Colluding Databases with Adversaries
• Caching and Delivery via Interference Elimination
• Fundamental Limits of Cache-Aided Private Information Retrieval with Unknown and Uncoded Prefetching
• Optimal Download Cost of Private Information Retrieval for Arbitrary Message Length
• Coded Caching Schemes with Reduced Subpacketization from Linear Block Codes
• On the Optimality of Separation between Caching and Delivery in General Cache Networks