@inproceedings{angel2018pir,
author = {Angel, Sebastian and Chen, Hao and Laine, Kim and Setty, Srinath},
title = {PIR with compressed queries and amortized computation},
booktitle = {IEEE Symposium on Security and Privacy, S&P (Oakland) 2018},
year = {2018},
month = {April},
abstract = {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.},
url = {http://approjects.co.za/?big=en-us/research/publication/pir-compressed-queries-amortized-computation/},
edition = {IEEE Symposium on Security and Privacy, S&P (Oakland) 2018},
}