On the Storage Cost of Private Information Retrieval
arXiv:1910.11973
Abstract
We consider the fundamental tradeoff between the storage cost and the download cost in private information retrieval systems, without any explicit structural restrictions on the storage codes, such as maximum distance separable codes or uncoded storage. Two novel outer bounds are provided, which have the following implications. When the messages are stored without any redundancy across the databases, the optimal PIR strategy is to download all the messages; on the other hand, for PIR capacity-achieving codes, each database can reduce the storage cost, from storing all the messages, by no more than one message on average. We then focus on the two-message two-database case, and show that a stronger outer bound can be derived through a novel pseudo-message technique. This stronger outer bound suggests that a precise characterization of the storage-download tradeoff may require non-Shannon type inequalities, or at least more sophisticated bounding techniques.
arXiv comment17 pages, 3 figures
References in corpus (10)
- Private Information Retrieval from Coded Databases with Colluding Servers
- Characterizing the Rate Region of the (4,3,3) Exact-Repair Regenerating Codes
- Symmetry, Outer Bounds, and Code Constructions: A Computer-Aided Investigation on the Fundamental Limits of Caching
- Non-Shannon Information Inequalities in Four Random Variables
- Approximating the Gaussian Multiple Description Rate Region Under Symmetric Distortion Constraints
- Lower Bound on the Redundancy of PIR Codes
- The Capacity of Private Information Retrieval with Partially Known Private Side Information
- Capacity-Achieving Private Information Retrieval Codes with Optimal Message Size and Upload Cost
- On the Capacity of Locally Decodable Codes
- User Manual CAI version-1.0: An Open-Source Toolbox for Computer-Aided Investigation on the Fundamental Limits of Information Systems
Cited by in corpus (4)
- Private Set Intersection: A Multi-Message Symmetric Private Information Retrieval Perspective
- Multi-Party Private Set Intersection: An Information-Theoretic Approach
- New Results on the Storage-Retrieval Tradeoff in Private Information Retrieval Systems
- The Capacity of Private Information Retrieval Under Arbitrary Collusion Patterns