Improved Storage for Efficient Private Information Retrieval

Understand

We consider the problem of private information retrieval from $N$ \emph{storage-constrained} databases.

• In this problem, a user wishes to retrieve a single message out of $M$ messages (of size $L$) without revealing any information about the identity of the message to individual databases.
• Each database stores $\mu ML$ symbols, i.e., a $\mu$ fraction of the entire library, where $\frac{1}{N} \leq \mu \leq 1$.
• Our goal is to characterize the optimal tradeoff curve for the storage cost (captured by $\mu$) and the normalized download cost ($D/L$).