Name
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. |
Year | DOI | Venue |
|---|---|---|
2018 | 10.1109/SP.2018.00062 | 2018 IEEE Symposium on Security and Privacy (SP) |
Keywords | DocType | ISSN |
private information retrieval,batch codes,PIR,FHE,multi query PIR | Conference | 1081-6011 |
ISBN | Citations | PageRank |
978-1-5386-4354-9 | 8 | 0.74 |
References | Authors | |
55 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Sebastian Angel | 1 | 31 | 8.25 |
| Hao Chen | 2 | 46 | 4.39 |
| Kim Laine | 3 | 93 | 9.83 |
| Srinath T. V. Setty | 4 | 384 | 16.40 |