Download Cost of Private Updating

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 ${\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\left(\genfrac{}{}{0ex}{}{L}{i}\right)\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.

To appear in the 2021 IEEE International Conference on Communications (ICC)