The Capacity of Private Information Retrieval from Uncoded Storage Constrained Databases

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 database scenario, where N databases store each of the K messages was considered by Sun and Jafar, and the optimal download cost was characterized as (1+ 1/N+ 1/N2+ ⋯ + 1/NK-1). In this work, we consider the problem of PIR from uncoded storage constrained databases. Each database has a storage capacity of μ KL bits, where L is the size of each message in bits, and μ in [1/N, 1] is the normalized storage. The novel aspect of this work is to characterize the optimum download cost of PIR from uncoded storage constrained databases for any 'normalized storage' value in the range μ in [1/N, 1]. In particular, for any (N,K), we show that the optimal trade-off between normalized storage, μ, and the download cost, D(μ), is a piece-wise linear function given by the lower convex hull of the N pairs (t/N, (1+ 1/t+ 1/t2+ ⋯ + 1/tK-1)) for t=1,2,⋯, N. To prove this result, we first present a storage constrained PIR scheme for any (N,K). Next, we obtain a general lower bound on the download cost for PIR, which is valid for any arbitrary storage architecture. The uncoded storage assumption is then applied which allows us to express the lower bound as a linear program (LP). Finally, we solve the LP to obtain tight lower bounds on the download cost for different regimes of storage, which match the proposed storage constrained PIR scheme.