Private Information Delivery We introduce the problem of private information delivery (PID), comprised of K messages, a user, and N servers (each holds M leq K messages) that wish to deliver one out of K messages to the user privately, i.e., without revealing the delivered message index to the user. The information theoretic capacity of PID is defined as the maximum number of bits of the desired message that can be privately delivered per bit of total communication to the user. For the PID problem with K messages, N servers and M messages stored per server, we show that the capacity is MK when N geq displaystyle fracKgcd(K,M)  (displaystyle fracMgcd(K,M)  1) left(displaystyle lfloorfracKMrfloor 1right).

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).