Towards Characterizing the Download Cost of Cache-Aided Private Updating â€

Funding Sponsor

National Science Foundation

Third Author's Department

Electronics & Communications Engineering Department

Find in your Library

https://doi.org/10.3390/e27080828

All Authors

Bryttany Stark Ahmed Arafa Karim Banawan

Document Type

Research Article

Publication Title

Entropy

Publication Date

8-1-2025

doi

10.3390/e27080828

Abstract

We consider the problem of privately updating a message out of K messages from N replicated and non-colluding databases where a user has an outdated version of the message (Formula presented.) of length L bits that differ from the current version (Formula presented.) in at most f bits. The user also has a cache containing coded combinations of the K messages (with a pre-specified structure), which are unknown to the N databases (unknown prefetching). The cache Z contains â„“ linear combinations from all K messages in the databases with (Formula presented.) being the caching ratio. The user needs to retrieve (Formula presented.) correctly using a private information retrieval (PIR) scheme without leaking information about the message index (Formula presented.) to any individual database. Our objective is to jointly design the prefetching (i.e., the structure of said linear combinations) and the PIR strategies to achieve the least download cost. We propose a novel achievable scheme based on syndrome decoding where the cached linear combinations in Z are designed to be bits pertaining to the syndrome of (Formula presented.) according to a specific linear block code. We derive a general lower bound on the optimal download cost for (Formula presented.), in addition to achievable upper bounds. The upper and lower bounds match for the cases when r is exceptionally low or high, or when (Formula presented.) messages for arbitrary r. Such bounds are derived by developing novel cache-aided arbitrary message length PIR schemes. Our results show a significant reduction in the download cost if (Formula presented.) when compared with downloading (Formula presented.) directly using typical cached-aided PIR approaches.

Link to Full Text
Find this item online

Share

COinS