Paper 2017/1142

PIR with compressed queries and amortized computation

Sebastian Angel and Hao Chen and Kim Laine and Srinath Setty

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 complementary 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 PIR query sent by the client is a vector containing a number of ciphertexts proportional to the size of the server’s database. We propose a new method to compresses this vector into a single ciphertext, thereby reducing network costs by over 120X. The second technique is a new data encoding called a probabilistic batch code (PBC). We use PBCs to build a multi-query PIR scheme that allows the server to amortize the computational cost of processing a batch of requests. The protocol achieves a 6.7X speedup over processing queries one at a time, and is significantly more efficient than related encodings. We apply our techniques to the Pung unobservable communication system which relies on a custom multi-query CPIR protocol for its privacy guarantees. Replacing Pung’s protocol with our schemes, we find that we can simultaneously reduce network costs by 33X and increase throughput by 2X.