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

By Amos Beimel, Yuval Ishai, Tal Malkin. 2004

231 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computational Theory and Mathematics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

Citations in the corpus

PIR with Compressed Queries and Amortized Query Processing (2018, methodology): “[12] is to perform preprocessing over the database in certain IT-PIR schemes to reduce the cost of future queries.”
Private Information Retrieval From MDS Coded Data in Distributed Storage Systems (2016, background): “A PIR scheme incurs many overheads on the DSS, including communication cost, computations [7], and connectivity; user contacts n instead of k nodes, as seen in Example 1.”
Polynomial Batch Codes for Efficient IT-PIR (2016, background): “Also note that when u = 1, the above queries are identical to t -private queries in Goldberg’s basic protocol.”
This Paper Is Included in the Proceedings of the 12th Usenix Symposium on Operating Systems Design and Implementation (osdi '16). Unobservable Communication over Fully Untrusted Infrastructure Unobservable Communication over Fully Untrusted Infrastructure (unknown): “Pung then introduces a private multi-retrieval scheme that departs from most prior approaches (e.g., [18] [64] [67] [86]) in two ways.”
Keyword Search and Oblivious Pseudorandom Functions (2005, background): “We note that the latter cost can be amortized over t non-adaptive queries [2, 18].”
A geometric approach to information-theoretic private information retrieval (2005, methodology): “To measure the efficiency of an algorithm with preprocessing, we use the definition of work in [8] which counts the number of precomputed and database bits that need to be read in order to respond to a query.”
A Survey on Private Information Retrieval (Column: Computational Complexity) (2004, background): “The following are known and are proven in [13].”
Can We Access a Database Both Locally and Privately? (2017, methodology): “The results of [BIM00] on PIR with preprocessing include a weak lower bound on the tradeoﬀ between storage and server computation, positive results in the multi-server model, and a barrier to proving strong negative results for single-server solutions with adaptive queries (see Appendix A).”
Robust Information-Theoretic Private Information Retrieval (2002, background): “Several extensions of the basic model of PIR have been considered in [12], [26], [34], [35], and [50].”
One (Block) Size Fits All: PIR and SPIR with Variable-Length Records via Multi-Block Queries (2013, background): “Barring any clever precomputation scheme (and associated auxiliary storage), the computational cost of any PIR protocol (information-theoretic or otherwise) must be at least linear in the size of the database, since the user cannot possibly learn anything about a database bit that the server does no”
The Best of Both Worlds: Combining Information-Theoretic and Computational PIR for Communication Efficiency (2014, background): “Several IT-PIR protocols have since been proposed [4, 14, 16, 17] that use similar non-collusion assumptions.”
Scalable and Private Media Consumption with Popcorn (2016, methodology): “Previous work [18] [68] has applied this observation to incorporate sub-cubic algorithms [29] [56] (resulting in fewer total operations than would be done without batching).”
First CPIR Protocol with Data-Dependent Computation (2009, background): “In the case of multiple servers, [3] constructed several sublinear-computation information-theoretically private information retrieval protocols.”
Cryptography from Anonymity (2006, background): “The question of amortizing the computational cost of PIR has been previously considered in [4] [32].”
Breaking the O(n/sup 1/(2k-1)/) barrier for information-theoretic Private Information Retrieval (2002, background): “These two extreme types of protocols, which can be realized in the information-theoretic setting, have various applications [13, 6].”