Skip to content

One server for the price of two: Simple and fast single-server private information retrieval

Authors: A. Henzinger; M. M. Hong; H. Corrigan-Gibbs; S. Meiklejohn; V. Vaikuntanathan
Year: 2023

type: scheme collection: sok-references status: auto

Links: ePrint 2022/949

Summary

Auto-extracted summary (unreviewed)

Introduces SimplePIR, a single-server private information retrieval scheme based on LWE in which the server performs under one 32-bit multiply-add per database byte, reaching 10 GB/s/core throughput close to memory bandwidth and to two-server PIR, at the cost of a 121 MB one-time hint and 242 KB per query for a 1 GB database. DoublePIR reduces the hint to 16 MB (345 KB per query, 7.4 GB/s/core), and both are applied with a new approximate-set-membership structure to private Certificate Transparency auditing with 16 MB/month download and 150 bytes per TLS connection.

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 privateinformation-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 modest communication overheads: 16 MB of download per month, along with 150 bytes per TLS connection.
Source: pdf

Extracted details

Field Value Source Confidence
contribution SimplePIR: fastest single-server PIR from LWE llm 0.90
contribution DoublePIR with a much smaller client hint llm 0.90
contribution novel data structure for approximate set membership llm 0.90
contribution private auditing for Certificate Transparency llm 0.90
contribution open-source implementation and comparative evaluation llm 0.90
schemes LWE-based linearly homomorphic encryption llm 0.90
schemes PIR llm 0.90
tasks private information retrieval llm 0.90
tasks Certificate Transparency auditing llm 0.90
hardware AWS c5n.metal instance (single thread) llm 0.90
security level 128-bit (lattice parameter n about 1024) llm 0.90
threat model single untrusted database server llm 0.90
interaction other llm 0.90
code url https://github.com/ahenzinger/simplepir (URL found in the full text) regex 0.50
code url https://github.com/ahenzinger/simplepir/tree/438b4590aceedf76c7588b03125dfc0db39e361f (URL found in the full text) regex 0.50
code url https://github.com/ahenzinger/simplepir/blob/main/README.md (URL found in the full text) regex 0.50
code url https://github.com/ahenzinger/simplepir llm 0.90
limitations relatively large communication costs (hint download) llm 0.90
limitations server work remains linear in database size; combining with sublinear PIR is left open llm 0.90
key result server throughput: 10.0 GB/s/core (SimplePIR, 1 GB database) llm 0.90
key result server throughput: 7.4 GB/s/core (DoublePIR, 1 GB database) llm 0.90
key result hint size: 121 MB (SimplePIR) vs 16 MB (DoublePIR) (1 GB database) llm 0.90
key result per-query communication: 242 KB (SimplePIR) vs 345 KB (DoublePIR) (1 GB database) llm 0.90
key result speed-up over prior single-server PIR: about 8x vs SpiralStreamPack, 30x vs Spiral (throughput on 1 GB database) llm 0.90
key result Certificate Transparency auditing overhead: 16 MB download per month plus 150 bytes per TLS connection (private CT auditing application) llm 0.90

SoK reference [50]

A. Henzinger, M. M. Hong, H. Corrigan-Gibbs, S. Meiklejohn, and V. Vaikuntanathan, “One server for the price of two: Simple and fast single-server private information retrieval,” in USENIX Security 2023: 32nd USENIX Security Symposium, J. A. Calandrino and C. Troncoso, Eds. Anaheim, CA, USA: USENIX Association, Aug. 9–11, 2023, pp. 3889–3905. [Online]. Available: https://www. usenix.org/conference/usenixsecurity23/presentation/henzinger

Listed on the reference page of the site.

Keyword mentions

Counts of vocabulary terms in the full text (first page of occurrence in brackets).

  • scheme: PIR 224 [p.1], BFV 4 [p.19], Paillier 4 [p.3], ElGamal 3 [p.16], Leveled / somewhat HE 3 [p.15], RSA 2 [p.16], Secret sharing 2 [p.15]
  • library: Concrete (Zama) 1 [p.5]
  • hardware: GPU 1 [p.16]
  • technique: Key switching 4 [p.3], Matrix multiplication 4 [p.6], Compiler 2 [p.31]
  • assumption: LWE 84 [p.3], Lattice-based 19 [p.2], 128-bit security 2 [p.5]
  • topic: Homomorphic encryption 23 [p.2], Benchmark 11 [p.12], Open source 10 [p.1]

Files

Path (under papers/) Collection Pages Size SHA-256 Note
references/sok-references/050_one-server-for-the-price-of-two-simple-and-fast-single-serve.pdf sok-references 33 840.6 KB 04c75ebcb84c

Database key: one-server-for-the-price-of-two-simple-and-fast-single-server-private · created 2026-11-05 · updated 2026-11-05 · edit with python3 tools/paperdb.py set one-server-for-the-price-of-two-simple-and-fast-single-server-private COLUMN VALUE