  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 $\hat{W}_\theta$ of length $L$ bits that differ
from the current version $W_\theta$ in at most $f$ bits. The user needs to
retrieve $W_\theta$ correctly using a private information retrieval (PIR)
scheme with the least number of downloads without leaking any information about
the message index $\theta$ 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_\theta$, 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_{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 < \frac{L}{2}$ compared with
downloading $W_\theta$ directly using classical PIR approaches without taking
the correlation between $W_\theta$ and $\hat{W}_\theta$ into consideration.
