One Server for the Price of Two: Simple and Fast Single-Server Private Information Retrieval
One Server for the Price of Two: Simple and Fast Single-Server Private Information Retrieval
复制标题
DOI：
--
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Alexandra Henzinger;Matthew M. Hong;Henry Corrigan-Gibbs;S. Meiklejohn;V. Vaikuntanathan
中科院分区：
文献类型：
--
作者：
Alexandra Henzinger;Matthew M. Hong;Henry Corrigan-Gibbs;S. Meiklejohn;V. Vaikuntanathan
我们提出了SimplePIR，这是迄今为止已知的最快的单服务器私有信息检索方案。SimplePIR的安全性基于带误差学习假设。为了回答客户端的查询，SimplePIR服务器对每个数据库字节执行少于一次32位乘法和一次32位加法运算。SimplePIR实现了10GB/秒/核心的服务器吞吐量，这接近机器的内存带宽以及最快的双服务器私有信息检索方案（需要非共谋服务器）的性能。SimplePIR具有相对较高的通信成本：要对1GB的数据库进行查询，客户端必须下载一个关于数据库内容的121MB的“提示”；此后，客户端可以进行无限制次数的查询，每次查询需要242KB的通信量。我们提出了第二种单服务器方案DoublePIR，它将提示缩小到16MB，但每次查询的通信量略高（345KB）且吞吐量略低（7.4GB/秒/核心）。最后，我们将我们新的私有信息检索方案与一种用于近似集合成员关系的新型数据结构一起应用于证书透明度中的私有审计任务。我们实现了一种比谷歌浏览器当前方法更强的隐私概念，但通信量是其13倍：每周下载16MB，每个TLS连接1.5KB。
. We present SimplePIR, the fastest single-server private information retrieval scheme known to date. SimplePIR’s security holds under the learning-with-errors assumption. To answer a client’s query, the SimplePIR server performs fewer than one 32-bit multiplication and one 32-bit addition per database byte. SimplePIR achieves 10 GB/s/core server throughput, which approaches the memory bandwidth of the machine and the performance of the fastest two-server private-information-retrieval schemes (which require non-colluding servers). SimplePIR has relatively large communication costs: to make queries to a 1 GB database, the client must download a 121 MB “hint” about the database contents; thereafter, the client may make an unbounded number of queries, each requiring 242 KB of communication. We present a second single-server scheme, DoublePIR, that shrinks the hint to 16 MB at the cost of slightly higher per-query communication (345 KB) and slightly lower throughput (7.4 GB/s/core). Finally, we apply our new private-information-retrieval schemes, together with a novel data structure for approximate set membership, to the task of private auditing in Certificate Transparency. We achieve a strictly stronger notion of privacy than Google Chrome’s current approach with 13 × more communication: 16 MB of download per week, along with 1.5 KB per TLS connection.