Cryptology ePrint Archive: Report 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.

Category / Keywords: cryptographic protocols / private information retrieval

Date: received 25 Nov 2017

Contact author: sebs at cs utexas edu

Available format(s): PDF | BibTeX Citation

Version: 20171127:133208 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]