UC Irvine

A private information retrieval (PIR) scheme is a mechanism that allows a user to retrieve any one out of K messages from N non-communicating replicated databases, each of which stores all K messages, without revealing anything (in the information theoretic sense) about the identity of the desired message index to any individual database. If the size of each message is L bits and the total download required by a PIR scheme from all N databases is D bits, then D is called the download cost and the ratio L/D is called an achievable rate. For fixed K,N in N , the capacity of PIR, denoted by C , is the supremum of achievable rates over all PIR schemes and over all message sizes, and was recently shown to be C=(1+1/N+1/N2+ cdots +1/N^K-1-1. In this paper, for arbitrary K and N , we explore the minimum download cost DL across all PIR schemes (not restricted to linear schemes) for arbitrary message lengths L under arbitrary choices of alphabet (not restricted to finite fields) for the message and download symbols. If the same M -ary alphabet is used for the message and download symbols, then we show that the optimal download cost in M -ary symbols is DL=LC. If the message symbols are in M -ary alphabet and the downloaded symbols are in M -ary alphabet, then we show that the optimal download cost in M -ary symbols, DL in (L'C), (L/C-1, (L'/C) -2, where L'= L M' M, i.e., the optimal download cost is characterized to within two symbols.