Towards Characterizing the Download Cost of Cache-Aided Private Updating

We consider the problem of privately updating a message out of <i>K</i> messages from <i>N</i> replicated and non-colluding databases where a user has an <i>outdated</i> version of the message W^θ of length <i>L</i> bits that differ from the current version Wθ in at most <i>f</i> bits. The user also has a cache containing coded combinations of the <i>K</i> messages (with a pre-specified structure), which are unknown to the <i>N</i> databases (unknown prefetching). The cache <i>Z</i> contains <i>ℓ</i> linear combinations from all <i>K</i> 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 <i>Z</i> 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 <i>r</i> is exceptionally low or high, or when K=3 messages for arbitrary <i>r</i>. Such bounds are derived by developing novel <i>cache-aided arbitrary message length</i> PIR schemes. Our results show a significant reduction in the download cost if f<L2 when compared with downloading Wθ directly using typical cached-aided PIR approaches.