Improved Storage for Efficient Private Information Retrieval 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 mu M L symbols, i.e., a mu fraction of the entire library, where frac1N leq mu leq 1. Our goal is to characterize the optimal tradeoff curve for the storage cost (captured by mu) 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 AttiaKumarTandon storage scheme, which was initially introduced by MaddahAliNiesen 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.

CapacityAchieving Private Information Retrieval Codes from MDSCoded Databases with Minimum Message Size We consider constructing capacityachieving linear codes with minimum message size for private information retrieval (PIR) from N noncolluding databases, where each message is coded using maximum distance separable (MDS) codes, such that it can be recovered from accessing the contents of any T databases. It is shown that the minimum message size (sometimes also referred to as the subpacketization factor) is significantly, in fact exponentially, lower than previously believed. More precisely, when Ku003eTtextbfgcd(N,T) where K is the total number of messages in the system and textbfgcd(cdot,cdot) means the greatest common divisor, we establish, by providing both novel code constructions and a matching converse, the minimum message size as textbflcm(NT,T), where textbflcm(cdot,cdot) means the least common multiple. On the other hand, when K is small, we show that it is in fact possible to design codes with a message size even smaller than textbflcm(NT,T).