Paper 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.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. Proceedings on Privacy Enhancing Technologies 2016(4)
DOI
10.1515/popets-2016-0036
Keywords
Private information retrievalbatch codesbatch queriesramp schemesefficiency
Contact author(s)
henry @ indiana edu
History
2016-06-07: received
Short URL
https://ia.cr/2016/598
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/598,
      author = {Ryan Henry},
      title = {Polynomial Batch Codes for Efficient IT-PIR},
      howpublished = {Cryptology ePrint Archive, Paper 2016/598},
      year = {2016},
      doi = {10.1515/popets-2016-0036},
      note = {\url{https://eprint.iacr.org/2016/598}},
      url = {https://eprint.iacr.org/2016/598}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.