Cache-Aided Private Information Retrieval with Partially Known 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. 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 receivesrN 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) as a function of K, N, r. For a fixed K, N, we develop an inner bound (converse) and an outer bound (achievability) for the D*(r) curve. The bounds match in general for the cases of very low caching ratio (r ≤ 1/NK-1) and very high caching ratio (r ≥ K-2/N2-3N+KN). 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 5/32.