Name
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 KL bits where 1/N <= mu <= 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 (1 + 1/t + 1/t(2) + . .. + 1/t(K-1))(-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)(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) problem (mu = 1) and SC-PIR problem, we propose a new SC-PIR design idea using novel storage placement schemes. The proposed schemes significantly reduce the message size requirement while still meeting the capacity of SC-PIR. In particular, the proposed SC-PIR schemes require the size of each file to be only L = Nt(K-1) compared to the state-of-the-art L = ((N)(t))t(K). |
Year | DOI | Venue |
|---|---|---|
2019 | 10.1109/ISIT.2019.8849767 | 2019 IEEE INTERNATIONAL SYMPOSIUM ON INFORMATION THEORY (ISIT) |
Field | DocType | Volume |
Discrete mathematics,Private information retrieval,Mathematics,Database,Message size | Journal | abs/1901.07490 |
Citations | PageRank | References |
1 | 0.36 | 5 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Nicholas Woolsey | 1 | 15 | 6.06 |
| Rong-Rong Chen | 2 | 70 | 10.31 |
| Mingyue Ji | 3 | 641 | 51.43 |