General constructions for information-theoretic private information retrieval

A Private Information Retrieval (PIR) protocol enables a user to retrieve a data item from a database while hiding the identity of the item being retrieved; specifically, in a t-private k-server PIR protocol the database is replicated among k servers, and the user's privacy is protected from any collusion of up to t servers. The main cost-measure of such protocols is the communication complexity of retrieving a single bit of data. This work addresses the information-theoretic setting for PIR, where the user's privacy should be unconditionally protected against computationally unbounded servers. We present a general construction, whose abstract components can be instantiated to yield both old and new families of PIR protocols. A main ingredient in the new protocols is a generalization of a solution by Babai, Gal, Kimmel, and Lokam for a communication complexity problem in the multiparty simultaneous messages model. Our protocols simplify and improve upon previous ones, and resolve some previous anomalies. In particular, we get (1) 1-private k-server PIR protocols with 0 (k(3)n(1/(2k- 1))) communication bits, where n is the database size; (2) t-private k-server protocols with O(n(1/[(2k- 1)/t])) communication bits, for any constant integers k > t >= 1; and (3) t-private k-server protocols in which the user sends O(log n) bits to each server and receives O(n(t/k+epsilon)) bits in return, for any constant integers k > t >= 1 and constant epsilon > 0. The latter protocols have applications to the construction of efficient families of locally decodable codes over large alphabets and to PIR protocols with reduced work by the servers. (c) 2005 Elsevier Inc. All rights reserved.