Improved Storage for Efficient Private Information Retrieval
share
We consider the problem of private information retrieval from Nstorage-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 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-Ali-Niesen in the context of the caching problem, and when there is no uncoded partial replication, our scheme reduces to Banawan-Ulukus storage scheme; in general, our scheme outperforms both.
READ FULL TEXT