Skip to content

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