The Capacity of Private Information Retrieval With Private Side Information Under Storage Constraints
We consider the problem of private information retrieval (PIR) of a single message out of <inline formula> <tex math notation="LaTeX"$K$ /tex math>/inline formula> messages from <inline formula> <tex math notation="LaTeX"$N$ /tex math>/inline formula> replicated and non colluding databases where a cache enabled user (retriever) of cache size <inline formula> <tex math notation="LaTeX"$S$ /tex math>/inline formula> 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 <inline formula> <tex math notation="LaTeX"$S$ /tex math>/inline formula> as <inline formula> <tex math notation="LaTeX"$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} /tex math>/inline formula> where <inline formula> <tex math notation="LaTeX"$M$ /tex math>/inline formula> is the number of side information messages and <inline formula> <tex math notation="LaTeX"$r_{i} /tex math>/inline formula> is the portion of the <inline formula> <tex math notation="LaTeX"$i$ /tex math>/inline formula>th side information message that is cached with <inline formula> <tex math notation="LaTeX"\sum _{i=1}{M} r_{i}=S$ /tex math>/inline formula> Based on this capacity result, we prove two facts: First, for a fixed memory size <inline formula> <tex math notation="LaTeX"$S$ /tex math>/inline formula> and a fixed number of accessible messages <inline formula> <tex math notation="LaTeX"$M$ /tex math>/inline formula> uniform caching achieves the lowest normalized download cost, i.e. <inline formula> <tex math notation="LaTeX"$r_{i}\frac {S}{M} /tex math>/inline formula> for <inline formula> <tex math notation="LaTeX"$i=1, \dots M$ /tex math>/inline formula> is optimum. Second, for a fixed memory size <inline formula> <tex math notation="LaTeX"$S$ /tex math>/inline formula> among all possible <inline formula> <tex math notation="LaTeX"$K \left \lceil{ {S} \right \rceil +1$ /tex math>/inline formula> uniform caching schemes, the uniform caching scheme which caches <inline formula> <tex math notation="LaTeX"$M=K$ /tex math>/inline formula> messages achieves the lowest normalized download cost.
IEEE Transactions on Information Theory