Fundamental Limits of Private Information Retrieval With Unknown Cache Prefetching

The fundamental limits of private information retrieval (PIR) with unknown cache prefetching at the user are investigated in this paper. To this end, a novel random linear combination (RLC)-based PIR scheme that can solve the basic PIR problem and its variation is proposed. The proposed scheme is based on random coding approach and achieves the capacity of the basic PIR asymptotically. Then, we investigate PIR with unknown cache prefetching (PIRC) problem at different cache-to-file size ratio. Specifically, we propose RLC-based PIRC method, which prefetches RLC-based side information and leverages them to retrieve desired information at small download cost. Furthermore, by applying time and memory sharing on the proposed RLC-based PIRC, RLC-based basic PIR and some other known approach in literature, we derive the achievable normalized download cost bound of PIRC. The derived achievable bound outperforms the existing bound in literature and the case study provides numerical results that verifies it.

Automated summary

This paper investigates the fundamental limits of private information retrieval (PIR) with unknown cache prefetching and proposes a novel random linear combination (RLC)-based PIR scheme to solve the basic PIR problem. By exploring PIR with unknown cache prefetching (PIRC) at different cache-to-file size ratios, it is shown that the RLC-based PIRC method can reduce download costs in retrieving desired information. The achievable normalized download cost bound of PIRC derived from the proposed RLC-based PIRC outperforms existing bounds in literature, as verified by numerical results in a case study.