Private Information Retrieval from Storage Constrained Databases -- Coded Caching meets PIR
share
Private information retrieval (PIR) allows a user to retrieve a desired message out of K possible messages from N databases without revealing the identity of the desired message. Majority of existing works on PIR assume the presence of replicated databases, each storing all the K messages. In this work, we consider the problem of PIR from storage constrained databases. Each database has a storage capacity of μ KL bits, where K is the number of messages, L is the size of each message in bits, and μ∈ [1/N, 1] is the normalized storage. In the storage constrained PIR problem, there are two key design questions: a) how to store content across each database under storage constraints; and b) construction of schemes that allow efficient PIR through storage constrained databases. The main contribution of this work is a general achievable scheme for PIR from storage constrained databases for any value of storage. In particular, for any (N,K), with normalized storage μ= t/N, where the parameter t can take integer values t ∈{1, 2, ..., N}, we show that our proposed PIR scheme achieves a download cost of (1+ 1/t+ 1/t^2+ ... + 1/t^K-1). The extreme case when μ=1 (i.e., t=N) corresponds to the setting of replicated databases with full storage. For this extremal setting, our scheme recovers the information-theoretically optimal download cost characterized by Sun and Jafar as (1+ 1/N+ ... + 1/N^K-1). For the other extreme, when μ= 1/N (i.e., t=1), the proposed scheme achieves a download cost of K. The interesting aspect of the result is that for intermediate values of storage, i.e., 1/N < μ <1, the proposed scheme can strictly outperform memory-sharing between extreme values of storage.
READ FULL TEXT