Private information retrieval (PIR) enables a user to retrieve a data item from a database, replicated among one or more servers, while hiding the identity of the retrieved item. This problem was suggested by Chor, Goldreich, Kushilevitz, and Sudan in 1995, and since then efficient protocols with sub-linear communication were suggested. However, in all these protocols the servers' computation for each retrieval is at least linear in the size of entire database, even if the user requires only a single bit. In this paper, we study the computational complexity of PIR. We show that in the standard PIR model, where the servers hold only the database, linear computation cannot be avoided. To overcome this problem we propose the model of PIR with preprocessing: Before the execution of the protocol each server may compute and store polynomially-many information bits regarding the database; later on, this information should enable the servers to answer each query of the user with more efficient computation. We demonstrate that preprocessing can significantly save work. In particular, we construct for any constants k ≥ 2 and > 0: (1) a k-server protocol with O(n 1/(2k−1) ) communication, O(n/ log 2k−2 n) work, and O(n 1+ ) storage; (2) a k-server protocol with O(n 1/k+ ) communication and work and n O(1) storage; (3) a computationally-private k-server protocol with O(n ) communication, O(n 1/k+ ) work, and n O(1) storage; and (4) a protocol with a polylogarithmic number of servers, polylogarithmic communication and work, and O(n 1+ ) storage. On the lower bounds front, we prove that the product of the extra storage used by the servers (i.e., in addition to the length of the database) and the expected amount of work is at least linear in n. Finally, we suggest two alternative models to saving computation, by batching queries and by allowing a separate off-line interaction per future query.
Theoretical work proves that the collective work required by the servers to answer a client's request scales at least linearly with the size of the database REF .
Reducing the servers' computation in private information retrieval: Pir with preprocessing
In CRYPTO 2000
Computer Science