Improved Storage for Efficient Private Information Retrieval
Karim Banawan, Batuhan Arasli, Şennur Ulukuş · 2019
We consider the problem of private information retrieval from N storage-constrained databases. In this problem, a user wishes to retrieve a single message out of M messages (of size L) without revealing any information about the identity of the message to individual databases. Each database stores μML symbols, i.e., a μ fraction of the entire library, where 1/N ≤ μ ≤ 1. Our goal is to characterize the optimal tradeoff 1 curve for the storage cost (captured by μ) and the normalized download cost (D/L). We show that the download cost can be reduced by employing a hybrid storage scheme that combines MDS coding ideas with uncoded partial replication ideas. When there is no coding, our scheme reduces to Attia-Kumar-Tandon storage scheme, which was initially introduced by Maddah-AliNiesen in the context of the caching problem, and when there is no uncoded partial replication, our scheme reduces to BanawanUlukus storage scheme; in general, our scheme outperforms both.