The Capacity of Private Information Retrieval from Uncoded Storage Constrained Databases

Understand

Private information retrieval (PIR) allows a user to retrieve a desired message from a set of databases without revealing the identity of the desired message.

• The replicated databases scenario was considered by Sun and Jafar, 2016, where $N$ databases can store the same $K$ messages completely.
• A PIR scheme was developed to achieve the optimal download cost given by $\left(1+ \frac{1}{N}+ \frac{1}{N^{2}}+ \cdots + \frac{1}{N^{K-1}}\right)$.
• In this work, we consider the problem of PIR from storage constrained databases.