Reducing the servers' computation in private information retrieval: PIR with preprocessing
Reducing the servers' computation in private information retrieval: PIR with preprocessing
复制标题
DOI：
10.1007/s00145-004-0134-y
复制
发表时间：
2004-03-01
影响因子：
3
通讯作者：
Malkin, T
中科院分区：
文献类型：
--
作者：
Beimel, A;Ishai, Y;Malkin, T
私有信息检索（PIR）使用户能够从数据库中检索数据项，在一个或多个服务器之间复制，同时隐藏检索项的身份。这个问题是由Chor，Goldreich，Kushilevitz和Sudan在1995年提出的，从那时起，提出了有效的次线性通信协议。然而，在所有这些协议中，服务器的每次检索的计算至少是线性的，在整个数据库的大小，即使用户只需要一个单一的bit.In本文中，我们研究的计算复杂性PIR。我们表明，在标准的PIR模型中，服务器只持有数据库，线性计算无法避免。为了克服这个问题，我们提出了模型的PIR与预处理：在执行协议之前，每个服务器可以计算和存储多项式的许多信息位的数据库，后来，这些信息应该使服务器回答每个查询的用户与更有效的computation.We证明预处理可以显着节省工作。尤其是。对于任意常数k ≥ 2且k> 0，我们构造了：（1）一个k-服务器协议，（n（1/（2k-1）通信，O（n/log（2k-2）n）工作，O（n（1+ n））存储;（2）k-服务器协议，（n（1/k+ n））通信和工作以及n（O（1））存储;（3）一个计算私有的k-服务器协议，其O（n（k））通信，O（n（1/k+ k））工作，和n（O（1））存储;和（4）一个协议，具有多对数数量的服务器，多对数通信和工作，和O（n（1+ k））存储。在下限方面，我们证明了服务器使用的额外存储的乘积（即，除了数据库的长度之外），并且期望的工作量至少与N成线性关系。最后，我们提出了两种替代模型，以节省计算，通过孵化查询，并允许一个单独的离线交互每未来的查询。
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, 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 greater than or equal to 2 and epsilon > 0: (1) a k-server protocol with O(n(1/(2k-1))) communication, O(n/log(2k-2) n) work, and O(n(1+epsilon)) storage; (2) a k-server protocol with O(n(1/k+epsilon)) communication and work and n(O(1)) storage; (3) a computationally private k-server protocol with O(n(epsilon)) communication, O(n(1/k+epsilon)) work, and n(O(1)) storage; and (4) a protocol with a polylogarithmic number of servers, polylogarithmic communication and work, and O(n(1+epsilon)) 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 hatching queries and by allowing a separate off-line interaction per future query.