TY - GEN

T1 - The Capacity of Uncoded Storage Constrained PIR

AU - Attia, Mohamed Adel

AU - Kumar, Deepak

AU - Tandon, Ravi

N1 - Funding Information:
This work was supported by the NSF grant CAREER-1651492.
Publisher Copyright:
© 2018 IEEE.

PY - 2018/8/15

Y1 - 2018/8/15

N2 - Private information retrieval (PIR) allows a user to retrieve a desired message out of K possible messages from N databases (DBs) without revealing the identity of the desired message. In this work, we consider the problem of PIR from uncoded storage constrained DBs. Each DB has a storage capacity of mu KL bits, where L is the size of each message in bits, and muin[1/N, 1] is the normalized storage. In the storage constrained PIR problem, there are two key challenges: a) construction of communication efficient schemes through storage content design at each DB that allow download efficient PIR; and b characterizing the optimal download cost via information-theoretic lower bounds. The novel aspect of this work is to characterize the optimum download cost of PIR with storage constrained DBs for any value of storage. In particular, for any (N, K), we show that the optimal tradeoff between storage (mu) and the download cost (D(mu)) is given by the lower convex hull of the pairs (frac t N(1+frac 1 t+frac 1 t 2+cdots+frac 1 t K-1)) for t = 1,2,..., N. The main contribution of this paper is the converse proof, i.e., obtaining lower bounds on the download cost for PIR as a function of the available storage.

AB - Private information retrieval (PIR) allows a user to retrieve a desired message out of K possible messages from N databases (DBs) without revealing the identity of the desired message. In this work, we consider the problem of PIR from uncoded storage constrained DBs. Each DB has a storage capacity of mu KL bits, where L is the size of each message in bits, and muin[1/N, 1] is the normalized storage. In the storage constrained PIR problem, there are two key challenges: a) construction of communication efficient schemes through storage content design at each DB that allow download efficient PIR; and b characterizing the optimal download cost via information-theoretic lower bounds. The novel aspect of this work is to characterize the optimum download cost of PIR with storage constrained DBs for any value of storage. In particular, for any (N, K), we show that the optimal tradeoff between storage (mu) and the download cost (D(mu)) is given by the lower convex hull of the pairs (frac t N(1+frac 1 t+frac 1 t 2+cdots+frac 1 t K-1)) for t = 1,2,..., N. The main contribution of this paper is the converse proof, i.e., obtaining lower bounds on the download cost for PIR as a function of the available storage.

UR - http://www.scopus.com/inward/record.url?scp=85052440706&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85052440706&partnerID=8YFLogxK

U2 - 10.1109/ISIT.2018.8437729

DO - 10.1109/ISIT.2018.8437729

M3 - Conference contribution

AN - SCOPUS:85052440706

SN - 9781538647806

T3 - IEEE International Symposium on Information Theory - Proceedings

SP - 1959

EP - 1963

BT - 2018 IEEE International Symposium on Information Theory, ISIT 2018

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 2018 IEEE International Symposium on Information Theory, ISIT 2018

Y2 - 17 June 2018 through 22 June 2018

ER -