Private Information Retrieval from Storage Constrained Databases - Coded Caching meets PIR

Maryam Abdul-Wahid, Firas Almoualem, Deepak Kumar, Ravi Tandon

Abstract

Private information retrieval (PIR) allows a user to retrieve a desired message out of $K$ possible messages from $N$ databases without revealing the identity of the desired message. Majority of existing works on PIR assume the presence of replicated databases, each storing all the $K$ messages. In this work, we consider the problem of PIR from storage constrained databases. Each database has a storage capacity of $\mu KL$ bits, where $K$ is the number of messages, $L$ is the size of each message in bits, and $\mu \in [1/N, 1]$ is the normalized storage. In the storage constrained PIR problem, there are two key design questions: a) how to store content across each database under storage constraints; and b) construction of schemes that allow efficient PIR through storage constrained databases. The main contribution of this work is a general achievable scheme for PIR from storage constrained databases for any value of storage. In particular, for any $(N,K)$, with normalized storage $\mu= t/N$, where the parameter $t$ can take integer values $t \in \{1, 2, \ldots, N\}$, we show that our proposed PIR scheme achieves a download cost of $\left(1+ \frac{1}{t}+ \frac{1}{t^{2}}+ \cdots + \frac{1}{t^{K-1}}\right)$. The extreme case when $\mu=1$ (i.e., $t=N$) corresponds to the setting of replicated databases with full storage. For this extremal setting, our scheme recovers the information-theoretically optimal download cost characterized by Sun and Jafar as $\left(1+ \frac{1}{N}+ \cdots + \frac{1}{N^{K-1}}\right)$. For the other extreme, when $\mu= 1/N$ (i.e., $t=1$), the proposed scheme achieves a download cost of $K$. The interesting aspect of the result is that for intermediate values of storage, i.e., $1/N < \mu <1$, the proposed scheme can strictly outperform memory-sharing between extreme values of storage.

Introduction

Private Information Retrieval (PIR) is a classic problem in cryptography and information theory: how can a user download a specific file from a set of $N$ databases without any single database learning which file was requested? Most existing PIR research assumes a "replicated" setting where every database stores all $K$ available messages. In the real world, however, storage is a finite resource.

This paper tackles the Storage Constrained PIR problem, where each database can only store a fraction ($\mu$) of the total library. The challenge is two-fold:

  1. Content Placement: How should we distribute pieces of the messages across the $N$ databases?
  2. Retrieval Strategy: How do we design a query/answer protocol that maintains privacy while minimizing the "download cost" (the total amount of data the user must download to get their message)?
System model for PIR with storage-constrained databases.

Methods

The authors propose a general achievable scheme that bridges the gap between PIR and Coded Caching. The method consists of two main components:

Storage Design (The "Coded Caching" part)

Inspired by the work of Maddah-Ali and Niesen, the authors split each message into sub-packets. Each sub-packet is indexed by a specific subset of databases. For a storage parameter $t$ (where normalized storage $\mu = t/N$), each sub-packet is stored in exactly $t$ databases. This creates structured "overlaps" between databases that the PIR scheme can exploit to create side information.

PIR Scheme (The "Symmetry" part)

The retrieval process happens in $K$ stages:

  • Stage 1: The user downloads individual bits of the desired and undesired messages to maintain privacy (message symmetry).
  • Stage 2 and beyond: The user exploits "side information" by downloading XORed combinations of bits. Crucially, in the storage-constrained setting, a bit from Database A can only serve as side information for Database B if Database B actually has that bit in its local storage. The proposed scheme carefully manages these constraints.

The authors also provide a formal proof that the optimal download cost is a convex function of the storage capacity, justifying the use of the lower convex hull of their discrete results for any arbitrary storage value.

Key Results

The paper characterizes an achievable download cost $D(\mu)$ for any $(N, K)$ pair with normalized storage $\mu = t/N$:

$$D(\mu) = 1 + \frac{1}{t} + \frac{1}{t^2} + \dots + \frac{1}{t^{K-1}}$$

The tradeoff between normalized storage $\mu$ and download cost $D(\mu)$, showing the achievable points and the lower convex hull.
  • Full Storage ($\mu=1, t=N$): The scheme recovers the information-theoretically optimal cost characterized by Sun and Jafar.
  • Minimum Storage ($\mu=1/N, t=1$): The scheme achieves a download cost of $K$, which is the best possible when each database only holds a unique piece of the data.
  • Beating Memory-Sharing: A naive approach to limited storage is "memory-sharing"—using a full-storage scheme for some bits and a minimum-storage scheme for others. This paper shows that a dedicated joint design can strictly outperform memory-sharing, providing a more efficient tradeoff between storage and communication.

Conclusion

This work demonstrates the synergy between coded caching and PIR. By using structured storage placement, one can significantly reduce the communication overhead of private retrieval. Future work includes finding matching lower bounds to prove capacity, and extending the model to handle database collusion or robustness against failures.

Summary updated

Abstract

Private information retrieval (PIR) allows a user to retrieve a desired message out of $K$ possible messages from $N$ databases without revealing the identity of the desired message. Majority of existing works on PIR assume the presence of replicated databases, each storing all the $K$ messages. In this work, we consider the problem of PIR from storage constrained databases. Each database has a storage capacity of $\mu KL$ bits, where $K$ is the number of messages, $L$ is the size of each message in bits, and $\mu \in [1/N, 1]$ is the normalized storage. In the storage constrained PIR problem, there are two key design questions: a) how to store content across each database under storage constraints; and b) construction of schemes that allow efficient PIR through storage constrained databases. The main contribution of this work is a general achievable scheme for PIR from storage constrained databases for any value of storage. In particular, for any $(N,K)$, with normalized storage $\mu= t/N$, where the parameter $t$ can take integer values $t \in \{1, 2, \ldots, N\}$, we show that our proposed PIR scheme achieves a download cost of $\left(1+ \frac{1}{t}+ \frac{1}{t^{2}}+ \cdots + \frac{1}{t^{K-1}}\right)$. The extreme case when $\mu=1$ (i.e., $t=N$) corresponds to the setting of replicated databases with full storage. For this extremal setting, our scheme recovers the information-theoretically optimal download cost characterized by Sun and Jafar as $\left(1+ \frac{1}{N}+ \cdots + \frac{1}{N^{K-1}}\right)$. For the other extreme, when $\mu= 1/N$ (i.e., $t=1$), the proposed scheme achieves a download cost of $K$. The interesting aspect of the result is that for intermediate values of storage, i.e., $1/N < \mu <1$, the proposed scheme can strictly outperform memory-sharing between extreme values of storage.
BibTeX
@inproceedings{abdulwahid2018private,
  author = {Maryam Abdul-Wahid and Firas Almoualem and Deepak Kumar and Ravi Tandon},
  title = {{Private Information Retrieval from Storage Constrained Databases - Coded Caching meets PIR}},
  booktitle = {ICC},
  year = {2018},
  url = {https://openreview.net/forum?id=5jVrabhkuZW},
}
Figure