Henzinger, Alexandra; Hong, Matthew M; Corrigan-Gibbs, Henry; Meiklejohn, Sarah; Vaikuntanathan, Vinod; (2023) One Server for the Price of Two: Simple and Fast Single-Server Private Information Retrieval. In: Proceedings of the 32nd USENIX Security Symposium. (pp. pp. 3889-3905). USENIX: Anaheim, CA, USA.

Preview

Text usenixsecurity23-henzinger.pdf - Published Version Download (779kB) | Preview

Abstract

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.

Download activity - last month

Export as JSONCSVXML

Download activity - last 12 months

Export as CSVXMLJSON

Downloads by country - last 12 months

Export as JSONXMLCSV

Archive Staff Only

View Item