XPIR : Private Information Retrieval for Everyone

By Carlos Aguilar Melchor, Joris Barrier, Laurent Fousse, Marc-Olivier Killijian. 2016

280 citations recorded by the source corpus.

Abstract A Private Information Retrieval (PIR) scheme is a protocol in which a user retrieves a record from a database while hiding which from the database administrators. PIR can be achieved using mutuallydistrustful replicated databases, trusted hardware, or cryptography. In this paper we focus on the later setting which is known as single-database computationally- Private Information Retrieval (cPIR). Classic cPIR protocols require that the database server executes an algorithm over all the database content at very low speeds which impairs their usage. In [1], given certain assumptions, realistic at the time, Sion and Carbunar showed that cPIR schemes were not practical and most likely would never be. To this day, this conclusion is widely accepted by researchers and practitioners. Using the paradigm shift introduced by lattice-based cryptography, we show that the conclusion of Sion and Carbunar is not valid anymore: cPIR is of practical value. This is achieved without compromising security, using standard crytosystems, and conservative parameter choices.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, 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 Computational Theory and Mathematics

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].”
Private Stateful Information Retrieval (2018, methodology): “We construct PSIR using XPIR [5] as well as a PIR construction built from the Paillier cryptosystem [43].”
PIR with Compressed Queries and Amortized Query Processing (2018, methodology): “For XPIR, we use the publicly available source code [9] and integrate it into our testing framework using Rust wrappers.”
Scalable and Private Media Consumption with Popcorn (2016, methodology): “Their performance, however, is still insufficient for our purposes: while the authors of the recent XPIRe system [7] report that “.”
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): “We focus on computational PIR (CPIR) schemes [10] [28] [30] [57] [58] [73] [77] [135] that hide users' access patterns under cryptographic hardness assumptions.”
Post-quantum Key Exchange - A New Hope (2016, unknown): “For some background on the NTT and the description of fast software implementations we refer to [45, 63].”
Communication-Computation Trade-offs in PIR (2019, methodology): “While theoretical constructions for PIR [45] achieve poly-logarithmic communication, most efficient single server PIR implementations stop short of this goal and implement only variants of the construction with higher asymptotic communication costs [5, 6, 38, 50].”
Compressible FHE with Applications to PIR (2019, methodology): “See [KLL + 15,AMBFK16,LP17] for more motivating discussions.”
Function Secret Sharing: Improvements and Extensions (2016, background): “Indeed all known single-server PIR protocols require (additively homomorphic) public-key encryption of the whole database to evaluate a PIR query (cf. [25] and references therein).”