Abstract
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 W_θ 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 \emph{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₂(Σ_i=0^f Li) is an integer. Our results imply that there is a significant reduction in the download cost if f < L/2 compared with downloading W_θ directly using classical PIR approaches without taking the correlation between W_θ and W_θ into consideration.