Optimal Download Cost of Private Information Retrieval for Arbitrary Message Length

Abstract

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 ϵ ℕ, 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/N <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> +⋯+1/N <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">K-1</sup> ) <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">-1</sup> . In this paper, for arbitrary K and N, we explore the minimum download cost D <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">L</sub> 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 D <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">L</sub> = ⌈L/C⌉. 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, D <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">L</sub> ϵ {⌈L'/C⌉, ⌈L'/C⌉-1, ⌈L'/C⌉ - 2}, where L' = ⌈L log <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">M'</sub> M⌉, i.e., the optimal download cost is characterized to within two symbols.