Reducing the Servers' Computation in Private Information Retrieval: PIR with Preprocessing

摘要

Private information retrieval (FIR) 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 severs 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, 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/2(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 polylogarthmic number of servers, polylogrithmic 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.