SPIRAL: Fast, high-rate single-server PIR via FHE composition¶
Authors: S. J. Menon; D. J. Wu
Year: 2022
type: scheme collection: sok-references status: auto
Links: ePrint 2022/368
Summary¶
Auto-extracted summary (unreviewed)
Spiral is a family of single-server private information retrieval protocols that composes two lattice-based homomorphic encryption schemes (Regev and Gentry-Sahai-Waters) using new ciphertext translation techniques, together with automated parameter selection based on a heuristic noise model. The basic version achieves at least 4.5x smaller queries, 1.5x smaller responses and 2x higher server throughput than prior systems, while the streaming variant SpiralStreamPack reaches 1.9 GB/s server throughput and a rate of 0.81 on million-record databases, with an estimated monetary cost only 1.9x that of the no-privacy download baseline.
Abstract¶
We introduce the Spiral family of single-server private information retrieval (PIR) protocols. Spiral relies on a composition of two lattice-based homomorphic encryption schemes: the Regev encryption scheme and the Gentry-Sahai-Waters encryption scheme. We introduce new ciphertext translation techniques to convert between these two schemes and in doing so, enable new trade-ofs in communication and computation. Across a broad range of database confgurations, the basic version of Spiral simultaneously achieves at least a 4.5× reduction in query size, 1.5× reduction in response size, and 2× increase in server throughput compared to previous systems. A variant of our scheme, SpiralStreamPack, is optimized for the streaming setting and achieves a server throughput of 1.9 GB/s for databases with over a million records (compared to 200 MB/s for previous protocols) and a rate of 0.81 (compared to 0.24 for previous protocols). For streaming large records (e.g., a private video stream), we estimate the monetary cost of SpiralStreamPack to be only 1.9× greater than that of the no-privacy baseline where the client directly downloads the desired record.
Source: pdf
Extracted details¶
| Field | Value | Source | Confidence |
|---|---|---|---|
| contribution | Spiral family of single-server PIR protocols via composition of Regev and GSW homomorphic encryption | llm | 0.85 |
| contribution | New ciphertext translation techniques between Regev and GSW encodings enabling communication/computation trade-offs | llm | 0.85 |
| contribution | SpiralStreamPack variant optimized for streaming large records | llm | 0.85 |
| contribution | Automated parameter selection with heuristic noise analysis validated empirically | llm | 0.85 |
| schemes | Regev encryption | llm | 0.85 |
| schemes | GSW | llm | 0.85 |
| schemes | RLWE | llm | 0.85 |
| libraries | Intel HEXL | llm | 0.85 |
| libraries | SEAL | llm | 0.85 |
| tasks | private information retrieval | llm | 0.85 |
| threat model | single untrusted server (no non-colluding servers assumption) | llm | 0.85 |
| interaction | non-interactive FHE | llm | 0.85 |
| code url | https://github.com/menonsamir/spiral.28 (URL found in the full text) | regex | 0.50 |
| code url | https://github.com/intel/hexl (URL found in the full text) | regex | 0.50 |
| code url | https://github.com/Microsoft/SEAL (URL found in the full text) | regex | 0.50 |
| code url | https://github.com/menonsamir/spiral | llm | 0.85 |
| limitations | Concrete parameters rely on the independence heuristic rather than worst-case bounds, at the expense of a possibly larger correctness error | llm | 0.85 |
| llm relevance | low | llm | 0.85 |
| key result | query size reduction: >=4.5x (basic Spiral vs previous systems) | llm | 0.85 |
| key result | response size reduction: 1.5x (basic Spiral vs previous systems) | llm | 0.85 |
| key result | server throughput increase: 2x (basic Spiral vs previous systems) | llm | 0.85 |
| key result | server throughput: 1.9 GB/s (vs 200 MB/s prior) (SpiralStreamPack, databases with over a million records) | llm | 0.85 |
| key result | rate: 0.81 (vs 0.24 prior) (SpiralStreamPack) | llm | 0.85 |
| key result | monetary cost overhead: 1.9x the no-privacy baseline (streaming large records) | llm | 0.85 |
SoK reference [51]¶
S. J. Menon and D. J. Wu, “SPIRAL: Fast, high-rate single-server PIR via FHE composition,” in 2022 IEEE Symposium on Security and Privacy. San Francisco, CA, USA: IEEE Computer Society Press, May 22–26, 2022, pp. 930–947.
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: GSW 136 [p.3], PIR 113 [p.1], BFV 7 [p.3], TFHE 3 [p.38], Paillier 2 [p.36], Oblivious transfer 2 [p.39], Leveled / somewhat HE 2 [p.3]
- library: Microsoft SEAL 3 [p.28]
- model: k-NN 1 [p.37]
- hardware: AVX-512 5 [p.28], Intel Xeon 1 [p.28]
- technique: Modulus switching 14 [p.13], Key switching 12 [p.4], Rescaling 7 [p.13], Bootstrapping 4 [p.3], SIMD packing 4 [p.2], NTT 4 [p.28], Pruning 2 [p.26]
- assumption: Lattice-based 38 [p.1], RLWE 10 [p.9], LWE 10 [p.9]
- task: Language modeling / generation 9 [p.5]
- topic: Homomorphic encryption 28 [p.1], Benchmark 4 [p.2], Open source 3 [p.28]
Files¶
| Path (under papers/) | Collection | Pages | Size | SHA-256 | Note |
|---|---|---|---|---|---|
references/sok-references/051_spiral-fast-high-rate-single-server-pir-via-fhe-composition.pdf |
sok-references | 46 | 877.4 KB | 6d8e22225641 |
Database key: spiral-fast-high-rate-single-server-pir-via-fhe-composition · created 2026-11-05 · updated 2026-11-05 · edit with python3 tools/paperdb.py set spiral-fast-high-rate-single-server-pir-via-fhe-composition COLUMN VALUE