Download Cost of Private Updating

We consider the problem of privately updating a message out of K messages from N replicated and non-colluding databases. In this problem, a user has an outdated version of the message Ŵ θ of length L bits that differ from the current version W θ in at most f bits. The user needs to retrieve W θ correctly using a private information retrieval (PIR) scheme with the least number of downloads without leaking any information about the message index θ to any individual database. To that end, we propose a novel achievable scheme based on syndrome decoding. Specifically, the user downloads the syndrome corresponding to W θ , according to a linear block code with carefully designed parameters, using the optimal PIR scheme for messages with a length constraint. We derive lower and upper bounds for the optimal download cost that match if the term ${\log _2}\left( \sum\nolimits_{i = 0}^f \binom L i \right)$ is an integer. Our results imply that there is a significant reduction in the download cost if $f θ directly using classical PIR approaches without taking the correlation between W θ and Ŵ θ into consideration.