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
Abstract

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.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint.
Keywords
Private Information Retrieval
Contact author(s)
ahenz @ csail mit edu
History
2022-09-04: last of 3 revisions
2022-07-22: received
See all versions
Short URL
https://ia.cr/2022/949
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2022/949,
      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{https://eprint.iacr.org/2022/949}},
      url = {https://eprint.iacr.org/2022/949}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.