Revisiting the Computational Practicality of Private Information Retrieval

By Femi G. Olumofin, Ian Goldberg. 2011

144 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Information Retrieval & Search, Privacy & Security

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 Information Retrieval & Search

In Privacy & Security

Citations in the corpus

Advances and Open Problems in Federated Learning (2019, background): “Recent results on PIR have shown dramatic reductions in the computational cost through the use of lattice-based cryptosystems [16, 313, 17, 25, 175].”
XPIR : Private Information Retrieval for Everyone (2016, methodology): “Instead of using a trusted hardware module, it is also possible to build efficient PIR protocols using replicated databases as shown by Olumofin and Goldberg [26].”
The Best of Both Worlds: Combining Information-Theoretic and Computational PIR for Communication Efficiency (2014, methodology): “This connection was used by Olumofin and Goldberg [23] to represent a home user’s connection in 2010.”
Optimally Robust Private Information Retrieval (2012, background): “Our work does not change the server side of Goldberg's protocol in any way; to see speeds for the server-side operations, see Olumofin and Goldberg's 2011 paper [29].”
Compressible FHE with Applications to PIR (2019, methodology): “However, Damg˚ard-Jurik is computationally too expensive to be used in practice for large-scale PIR [SC07,OG11], at a minimum, PIR using Damg˚ard-Jurik requires the server to compute a mod-N multiplication per bit of the database, where N has 2048 or more bits.”
Single-Database Private Information Retrieval from Fully Homomorphic Encryption (2013, background): “Goldberg [29] analyzed the performance of the lattice-”
Scalable and Private Media Consumption with Popcorn (2016, methodology): “[61] found that the fastest known CPIR protocols [8] are approximately 10-100× slower than ITPIR protocols [20, 36].”
Sublinear Scaling for Multi-Client Private Information Retrieval (2015, background): “Goldberg’s PIR scheme is most efficient when the number of blocks equals the number of field elements per block [12].”
PIR-Tor: Scalable Anonymous Communication Using Private Information Retrieval (2011, methodology): “The CPIR scheme is the best-performing single-server scheme [32], and both are available as open-source libraries.”
Optimal Rate Private Information Retrieval from Homomorphic Encryption (2015, background): “See [14, 15, 31] and references therein for other possible optimizations.”
One (Block) Size Fits All: PIR and SPIR with Variable-Length Records via Multi-Block Queries (2013, methodology): “We focus on Goldberg’s IT-PIR for three reasons: 1) IT-PIR protocols like Goldberg’s protocol are faster than any known CPIR protocol by an order of magnitude or more [34], 2) the communication cost of Goldberg’s protocol is within a small factor of optimal if the user is interested in a relatively ”
Polynomial Batch Codes for Efficient IT-PIR (2016, background): “The privacy guarantees of such encryption-based PIR follow directly from the IND-CPA security of the underlying encryption scheme against computationally bounded attackers; thus, such protocols are called computationally secure PIR (CPIR) protocols.”