Cache-Aided Private Information Retrieval with Unknown and Uncoded Prefetching
Yi-Peng Wei, Karim Banawan, Şennur Ulukuş · 2018
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, r. We develop inner and outer bounds for the optimal download cost. Both inner and outer bounds are piece-wise linear functions in r (for fixed N, K) that consist of K line segments. The inner and the outer bounds match in general for the cases of very low caching ratios and very high caching ratios. 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 additive gap between the achievability and the converse bounds is [1/6].