Paper 2022/949

One Server for the Price of Two: Simple and Fast Single-Server Private Information Retrieval

Alexandra Henzinger, Massachusetts Institute of Technology
Matthew M. Hong, Massachusetts Institute of Technology
Henry Corrigan-Gibbs, Massachusetts Institute of Technology
Sarah Meiklejohn, Google
Vinod Vaikuntanathan, Massachusetts Institute of Technology

We present SimplePIR, the fastest private information retrieval (PIR) scheme known to date. SimplePIR is a single-server PIR scheme, whose security holds under the learning-with-errors assumption. To answer a client’s PIR query, the SimplePIR server performs one 32-bit multiplication and one 32-bit addition per database byte. SimplePIR achieves 6.5 GB/s/core server throughput, which is 7% faster than the fastest two-server PIR 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 124 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 (5.2 GB/s/core). Finally, we apply our PIR schemes, together with a new data structure for approximate set membership, to the problem of private auditing in Certificate Transparency. We achieve a strictly stronger notion of privacy than Google Chrome’s current approach with a modest, 13× larger communication overhead.

Available format(s)
Cryptographic protocols
Publication info
Private Information Retrieval
Contact author(s)
ahenz @ csail mit edu
2022-09-04: last of 3 revisions
2022-07-22: received
See all versions
Short URL
Creative Commons Attribution


      author = {Alexandra Henzinger and Matthew M. Hong and Henry Corrigan-Gibbs and Sarah Meiklejohn and Vinod Vaikuntanathan},
      title = {One Server for the Price of Two: Simple and Fast Single-Server Private Information Retrieval},
      howpublished = {Cryptology ePrint Archive, Paper 2022/949},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.