Towards Characterizing the Download Cost of Cache-Aided Private Updating

Area of Science:

• Information Theory
• Computer Science
• Cryptography

Background:

• Users often possess outdated versions of messages stored across multiple databases.
• Existing cache-aided private information retrieval (PIR) schemes face challenges in optimizing download costs.
• Unknown prefetching strategies by users complicate database interactions.

Purpose of the Study:

• To jointly design prefetching and PIR strategies for minimizing download costs when updating messages.
• To develop a novel cache-aided PIR scheme for retrieving updated messages from replicated databases.
• To analyze the trade-offs between caching ratio and download efficiency.

Main Methods:

• A novel PIR scheme based on syndrome decoding is proposed, utilizing cached linear combinations as syndrome bits.
• General lower and achievable upper bounds on the optimal download cost are derived.
• Cache-aided arbitrary message length PIR schemes are developed to establish these bounds.

Main Results:

• The proposed scheme demonstrates significant download cost reduction when the number of differing bits (f) is less than half the message length (L/2).
• Achieved upper and derived lower bounds on download cost coincide for specific scenarios: low/high caching ratios (r) or K=3 messages.
• The effectiveness of the joint design is validated across various parameters.

Conclusions:

• The proposed syndrome decoding-based PIR scheme offers a significant improvement in download efficiency for updating messages from replicated databases.
• The developed bounds provide theoretical insights into the optimal performance of cache-aided PIR systems.
• The joint optimization of prefetching and PIR is crucial for minimizing data retrieval costs in distributed systems.