Towards Characterizing the Download Cost of Cache-Aided Private Updating

We consider the problem of privately updating a message out of K messages from N replicated and non-colluding databases where a user has an outdated version of the message W^θ of length L bits that differ from the current version Wθ in at most f bits. The user also has a cache containing coded combinations of the K messages (with a pre-specified structure), which are unknown to the N databases (unknown prefetching). The cache Z contains ℓ linear combinations from all K messages in the databases with r=lL being the caching ratio. The user needs to retrieve Wθ correctly using a private information retrieval (PIR) scheme without leaking information about the message index θ to any individual database. Our objective is to jointly design the prefetching (i.e., the structure of said linear combinations) and the PIR strategies to achieve the least download cost. We propose a novel achievable scheme based on syndrome decoding where the cached linear combinations in Z are designed to be bits pertaining to the syndrome of Wθ according to a specific linear block code. We derive a general lower bound on the optimal download cost for 0≤r≤1, in addition to achievable upper bounds. The upper and lower bounds match for the cases when r is exceptionally low or high, or when K=3 messages for arbitrary r. Such bounds are derived by developing novel cache-aided arbitrary message length PIR schemes. Our results show a significant reduction in the download cost if f