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