Cryptology ePrint Archive: Report 2016/598

Polynomial Batch Codes for Efficient IT-PIR

Ryan Henry

Abstract: Private information retrieval (PIR) is a way for clients to query a remote database without the database holder learning the clients' query terms or the responses they generate. Compelling applications for PIR are abound in the cryptographic and privacy research literature, yet existing PIR techniques are notoriously inefficient. Consequently, no such PIR-based application to date has seen real-world at-scale deployment. This paper proposes new "batch coding" techniques to help address PIR's efficiency problem. The new techniques exploit the connection between ramp secret sharing schemes and efficient information-theoretically secure PIR (IT-PIR) protocols. This connection was previously observed by Henry, Huang, and Goldberg (NDSS 2013), who used ramp schemes to construct efficient "batch queries" with which clients can fetch several database records for the same cost as fetching a single record using a standard, non-batch query. The new techniques in this paper generalize and extend those of Henry et al. to construct "batch codes" with which clients can fetch several records for only a fraction the cost of fetching a single record using a standard non-batch query over an unencoded database. The batch codes are highly tuneable, providing a means to trade off (i) lower server-side computation cost, (ii) lower server-side storage cost, and/or (iii) lower uni- or bi-directional communication cost, in exchange for a comparatively modest decrease in resilience to Byzantine database servers.

Category / Keywords: cryptographic protocols / Private information retrieval, batch codes, batch queries, ramp schemes, efficiency

Original Publication (in the same form): Proceedings on Privacy Enhancing Technologies 2016(4)

Date: received 6 Jun 2016

Contact author: henry at indiana edu

Available format(s): PDF | BibTeX Citation

Version: 20160607:202623 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]