Paper 2017/1142
PIR with compressed queries and amortized query processing
, The University of Texas at Austin, New York UniversityAbstract
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.
Note: This version fixes a typo in Figure 4.
Metadata
- Available format(s)
-
PDF
- Publication info
- Published elsewhere. Minor revision. IEEE Security and Privacy 2018 (Oakland)
- Keywords
- PIRprivate information retrievalbatch codes
- Contact author(s)
- sebastian angel @ cis upenn edu
- History
- 2024-06-20: last of 4 revisions
- 2017-11-27: received
- See all versions
- Short URL
- https://ia.cr/2017/1142
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2017/1142,
author = {Sebastian Angel and Hao Chen and Kim Laine and Srinath Setty},
title = {{PIR} with compressed queries and amortized query processing},
howpublished = {Cryptology ePrint Archive, Paper 2017/1142},
year = {2017},
note = {\url{https://eprint.iacr.org/2017/1142}},
url = {https://eprint.iacr.org/2017/1142}
}
