| Paper Title |
A New Design of Private Information Retrieval for Storage Constrained Databases |
| Paper Identifier | TU3.R3.3 |
|---|
| Authors |
Nicholas Woolsey, Rong-Rong Chen, Mingyue Ji, University of Utah, United States |
| Session |
Private Information Retrieval II |
| Location |
Monge, Level 3 |
| Session Time |
Tuesday, 09 July, 14:30 - 16:10 |
| Presentation Time |
Tuesday, 09 July, 15:10 - 15:30 |
| Manuscript |
Click here to download the manuscript |
| Abstract
| Private information retrieval (PIR) allows a user to download one of $K$ messages from $N$ databases without revealing to any database which of the $K$ messages is being downloaded. In general, the databases can be storage constrained where each database can only store up to $\mu K L$ bits where $\frac{1}{N} \leq \mu \leq 1$ and $L$ is the size of each message in bits. Let $t= \mu N$, a recent work showed that the capacity of Storage Constrained PIR (SC-PIR) is $\left( 1+ \frac{1}{t} + \frac{1}{t^2} + \cdots + \frac{1}{t^{K-1}} \right)^{-1}$, which is achieved by a storage placement scheme inspired by the content placement scheme in the literature of coded caching and the original PIR scheme. Not surprisingly, this achievable scheme requires that each message is $L = {N \choose t}t^K$ bits in length, which can be impractical. In this paper, without trying to make the connection between SC-PIR and coded caching problems, based on a general connection between the Full Storage PIR (FS-PIR) problems ($\mu = 1$) and SC-PIR problems, we propose a new SC-PIR design idea using novel storage placement schemes. The proposed schemes %that significantly reduce the message size requirement while still meeting the capacity of SC-PIR. In particular, the proposed SC-PIR schemes requires each file to be only $L = Nt^{K-1}$ compared to the state-of-the-art $L = {N \choose t}t^K$. |
