Polynomial Batch Codes for Efficient IT-PIR
Polynomial Batch Codes for Efficient IT-PIR
复制标题
DOI：
10.1515/popets-2016-0036
复制
发表时间：
2016-10
影响因子：
--
通讯作者：
Ryan Henry
中科院分区：
文献类型：
--
作者：
Ryan Henry
摘要私有信息检索(PIR)是一种客户查询远程数据库的方式，数据库持有者不需要学习客户的查询条件或他们生成的响应。PIR的引人注目的应用在密码学和隐私研究文献中比比皆是，但现有的PIR技术效率低下是出了名的。因此，到目前为止，还没有这样的基于PIR的应用程序在现实世界中大规模部署。本文提出了一种新的“批处理编码”技术来解决PIR的效率问题。新技术利用了RAMP秘密共享方案和有效的信息理论上安全的PIR(IT-PIR)协议之间的联系。Henry、Huang和Goldberg(NDSS 2013)之前就观察到了这种联系，他们使用渐变方案构建了高效的“批处理查询”，使用这些查询，客户端可以获取多个数据库记录，而成本与使用标准的非批处理查询获取单个记录的成本相同。本文中的新方法推广和推广了Henry等人的方法。构建“批处理代码”，客户可以使用它来获取多个记录，而成本仅为在未编码的数据库上使用标准的非批处理查询获取单个记录的一小部分。批处理代码是高度可调的，提供了一种权衡(I)较低的服务器端计算成本、(Ii)较低的服务器端存储成本和/或(Iii)较低的单向或双向通信成本的手段，以换取对拜占庭数据库服务器的相对适度的弹性降低。
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 PIRbased 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.