New Results on the Storage-Retrieval Tradeoff in Private Information Retrieval Systems

Tao Guo, Ruida Zhou, Chao Tian

Introduction

Private Information Retrieval (PIR) allows a user to retrieve a specific message from a set of $N$ servers without any individual server knowing which message was requested. While traditional research focused on the "capacity" of PIR—the minimum download cost $\beta$—it often assumed messages are fully replicated across all servers. However, full replication is costly. In practice, there is a fundamental tradeoff: by allowing servers to store more data (higher storage cost $\alpha$), the amount of data the user needs to download (retrieval cost $\beta$) can often be reduced.

The 2-Approximate Characterization

Characterizing the optimal tradeoff curve is notoriously difficult. Even for simple cases, the exact curve was previously unknown because existing tools, like entropic Linear Programs (LPs), suffer from exponential complexity.

This paper provides a significant breakthrough by establishing a regime-wise 2-approximate characterization of the optimal tradeoff. The authors prove that the optimal performance is always within a factor of 2 of a simple baseline, providing a "sanity check" for the field and showing that existing codes are often closer to the optimum than previously thought.

Figure 2: (a) Simple approximation of the tradeoff curve. (b) Comparison between the approximation and the generalized MDS-PIR bound.

Methodological Innovations

The authors attack the problem using both "top-down" achievable codes and "bottom-up" mathematical lower bounds:

  • Cyclic Permutation Lemma: This novel "meta-technique" allows researchers to take a simple PIR code designed for $N$ servers and "rotate" it across a larger set of $M$ servers. This generates complex new codes from simpler building blocks and reveals that many specialized codes are applications of this general principle.
  • Relaxed Entropic LP: To find tighter lower bounds, the authors identified a subset of information-theoretic inequalities (submodularity, monotonicity, privacy, and invariance) that capture the essence of PIR. By enforcing message and server symmetry, they reduced the LP complexity from exponential to polynomial ($O(KN^8)$), allowing it to be solved for much larger systems.

Key Results and Performance

The paper introduces two new code designs, Construction-A and Construction-B. Notably, Construction-B outperforms standard Maximum Distance Separable (MDS)-PIR codes in download efficiency for the same storage cost.

Numerical simulations for configurations like $(N,K) = (5,3)$ show that the new relaxed LP produces bounds that "sandwich" the optimal tradeoff much more tightly than previous state-of-the-art methods. These results demonstrate that the new lower bounds are significantly closer to achievable upper bounds than any previous work in the literature.

Conclusion and Future Work

While the gap between upper and lower bounds has been significantly reduced, it is not yet closed. Future work will involve identifying additional information-theoretic constraints to further refine the relaxed LP. Additionally, the authors plan to investigate if the cyclic permutation lemma can be combined with more exotic storage codes to find new "sweet spots" on the tradeoff curve.

Summary updated

BibTeX
@article{guo2021new,
  author = {Tao Guo and Ruida Zhou and Chao Tian},
  title = {{New Results on the Storage-Retrieval Tradeoff in Private Information Retrieval Systems}},
  journal = {IEEE J. Sel. Areas Inf. Theory},
  year = {2021},
  doi = {10.1109/jsait.2021.3053217},
}
Figure