Fundamental Limits of Cache-Aided Private Information Retrieval With Unknown and Uncoded Prefetching

作     者：Wei, Yi-Peng Banawan, Karim Ulukus, Sennur 

作者机构：Univ Maryland Dept Elect & Comp Engn College Pk MD 20742 USA 

出 版 物：《IEEE TRANSACTIONS ON INFORMATION THEORY》 (IEEE信息论汇刊)

年 卷 期：2019年第65卷第5期

页      面：3215-3232页

核心收录：

学科分类：0808[工学-电气工程] 08[工学] 0701[理学-数学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：NSF [CNS 13-14733  CCF 14-22111  CNS 15-26608  CCF 17-13977] 

主　　题：Private information retrieval caching uncoded prefetching PIR capacity side information 

摘      要：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.