Download Cost of Private Updating
Bryttany Herren, Ahmed M. Arafa, Karim Banawan · 2021
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 olimits_{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.