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 from each of the K stored messages in the databases. We assume that the databases are unaware of the cache content. We investigate D*(r) the optimal download cost normalized with the message size as a function of K, N, and r. For a fixed K and N, we develop an inner bound (converse bound) for the D*(r) curve. The inner bound is a piece-wise linear function in r that consists of K line segments. For the achievability, we develop explicit schemes that exploit the cached bits as side information to achieve K -1 non-degenerate corner points. These corner points differ in the number of cached bits that are used to generate the one-side information equation. We obtain an outer bound (achievability) for any caching ratio by memory sharing between these corner points. Thus, the outer bound is also a piece-wise linear function in r that consists of K line segments. The inner and the outer bounds match in general for the cases of very low-caching ratio and very high-caching ratio. As a corollary, 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 1/6. Our results show that the download cost can be reduced beyond memory sharing if the databases are unaware of the cached content.
7 June 2018 in IEEE Journal on Selected Areas in Communications
We consider the problem of private information retrieval 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 r/N uncoded fraction of each message from the nth database. This side information is known only to the nth database and unknown to the remaining databases, i.e., the user possesses partially known side information. We investigate the optimal normalized download cost D*(r) in the retrieval phase as a function of K, N, and 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 and very high caching ratio. We fully characterize the optimal download cost caching ratio tradeoff for K = 3. For general K, N, and r values, we show that the largest additive gap between the achievability and the converse bounds is 5/32.
19 August 2019 in IEEE Transactions on Information Theory
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} \leq M$ . In the retrieval phase, the user wishes to retrieve a message (which is not present in its memory) 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 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-\left({\frac {1}{N}}\right)^{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.
8 January 2020 in IEEE Transactions on Information Theory
We consider private information retrieval (PIR) of a single file out of K files from N non-colluding databases with heterogeneous storage constraints ${{m}}=({m}_{1}, \cdots,{m}_{{N}})$ . The aim of this work is to jointly design the content placement phase and the information retrieval phase in order to minimize the download cost in the PIR phase. We characterize the optimal PIR download cost as a linear program. By analyzing the structure of the optimal solution of this linear program, we show that, surprisingly, the optimal download cost in our heterogeneous case matches its homogeneous counterpart where all databases have the same average storage constraint $\mu =\frac {1}{{N}} \sum _{{n}=1}^{N} {m}_{{n}}$ . Thus, we show that there is no loss in the PIR capacity due to heterogeneity of storage spaces of the databases. We provide the optimum content placement explicitly for N = 3.
18 November 2019 in IEEE Transactions on Information Theory
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 where the message identities 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^{*}=1+\frac {1}{N}+\frac {1}{N^{2}}+ {\dots }+\frac {1}{N^{K-1-M}}+ \frac {1-r_{M}}{N^{K-M}}+\frac {1-r_{M-1}}{N^{K-M+1}}+ {\dots }+\frac {1-r_{1}}{N^{K-1}}$ , where $M$ is the number of side information messages and $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-\left \lceil{ {S} }\right \rceil +1$ uniform caching schemes, the uniform caching scheme which caches $M=K$ messages achieves the lowest normalized download cost.
We consider the private information retrieval (PIR) problem from decentralized uncoded caching databases. There are two phases in our problem setting, a caching phase, and a retrieval phase. In the caching phase, a data center containing all the K files, where each file is of size L bits, and several databases with storage size constraint bits exist in the system. Each database independently chooses bits out of the total bits from the data center to cache through the same probability distribution in a decentralized manner. In the retrieval phase, a user (retriever) accesses N databases in addition to the data center, and wishes to retrieve a desired file privately. We characterize the optimal normalized download cost to be . We show that uniform and random caching scheme which is originally proposed for decentralized coded caching by Maddah-Ali and Niesen, along with Sun and Jafar retrieval scheme which is originally proposed for PIR from replicated databases surprisingly results in the lowest normalized download cost. This is the decentralized counterpart of the recent result of Attia, Kumar, and Tandon for the centralized case. The converse proof contains several ingredients such as interference lower bound, induction lemma, replacing queries and answering string random variables with the content of distributed databases, the nature of decentralized uncoded caching databases, and bit marginalization of joint caching distributions.