PIR with Compressed Queries and Amortized Query Processing

By Sebastian Angel, Hao Chen, Kim Laine, Srinath T. V. Setty. 2018

364 citations recorded by the source corpus.

Private information retrieval (PIR) is a key building block in many privacy-preserving systems. Unfortunately, existing constructions remain very expensive. This paper introduces two techniques that make the computational variant of PIR (CPIR) more efficient in practice. The first technique targets a recent class of CPU-efficient CPIR protocols where the query sent by the client contains a number of ciphertexts proportional to the size of the database. We show how to compresses this query, achieving size reductions of up to 274X. The second technique is a new data encoding called probabilistic batch codes (PBCs). We use PBCs to build a multi query PIR scheme that allows the server to amortize its computational cost when processing a batch of requests from the same client. This technique achieves up to 40× speedup over processing queries one at a time, and is significantly more efficient than related encodings. We apply our techniques to the Pung private communication system, which relies on a custom multi-query CPIR protocol for its privacy guarantees. By porting our techniques to Pung, we find that we can simultaneously reduce network costs by 36× and increase throughput by 3X.

Subfields: Artificial Intelligence, Efficiency & Compression, 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 Efficiency & Compression

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].”
Secure Federated Submodel Learning (2019, methodology): “To avoid downloading the full matrix, Private Information Retrieval (PIR) [13]–[15] can be applied, which exactly matches our problem settings, including the read-only mode and the privacy preservation requirement of the retrieved elements.”
Private Stateful Information Retrieval (2018, methodology): “Our experimental database contains n = 216, 218, 220 records of 288 bytes and to match the experiments of previous works [7, 8].”
On Deploying Secure Computing Commercially: Private Intersection-Sum Protocols and their Business Applications (2019, background): “([2] give one example of how to do so.”
Labeled PSI from Fully Homomorphic Encryption with Malicious Security (2018, methodology): “Pung also optimized for the multi-query using hashing techniques.”
Communication-Computation Trade-offs in PIR (2019, methodology): “[5] (based on latticebased additively homomorphic encryption).”
Compressible FHE with Applications to PIR (2019, methodology): “On the other hand, our scheme needs entry-size above 100KB to approach top performance, while the performance numbers from [ACLS18] are for 288-byte entries.”