🌐 Comparative benchs

PIR Engineering Notes

TLDR: Deep reading of PIR papers to extract eng. notes (eg) and visualize comparative benchs/asymptotics. The correctness of these notes are continuously validated:

• Scheme grouping based on this taxonomy (client state architecture)
• Multi-server schemes are excluded
• Engineering notes (eg) for 30 Private Information Retrieval (PIR) scheme entries with validated [2] footnotes
• Per-scheme notes are produced by reading the source PDF (incl. tables/figures which Claude can do) using a standardized methodology.
• Classification rationale for each scheme is documented in research/README.md

Group 1a — Stateless Client, Stateful Server

Server caches per-client cryptographic material (evaluation keys). Queries linkable across sessions.

Paper	Key Contribution
2026 NPIR	NTRU packing for high communication rate
2025 VIA-BC	VIA-C/VIA-B variants: LWE-to-RLWE query compression + batch repacking; 14.8 MB per-client eval keys
2025 OnionPIRv2	Multi-base decomposition + NTT-domain DB engineering
2025 Pirouette	36-byte queries via blind rotation
2024 WhisPIR	BGV-based, non-compact BGV optimization
2024 Respire	Small-record optimization, 5-ring architecture
2022 Spiral	Ciphertext translation (Regev-to-GSW), 4 Pareto-optimal variants
2022 CwPIR	Constant-weight equality operators, native keyword PIR
2021 FastPIR/Addra	System: metadata-private voice via one-hot BFV selection
2021 OnionPIR	External products for noise control, first <1s at scale
2019 MulPIR	GSW-based compressible FHE for high communication rate
2018 SealPIR	Query compression via BFV oblivious expansion (paradigm shift)
2016 XPIR-2016	Ring-LWE system with auto-optimization of parameters
2014 XPIR-2014	First practical NTRU-based single-server cPIR

Group 1b — Stateless Client, Stateless Server

No per-client state anywhere. Server preprocesses DB into a shared structure.

Paper	Key Contribution
2025 VIA	DMux-CMux architecture, fully hintless (base variant)
2025 InsPIRe	InspiRING ring packing, polynomial evaluation
2024 YPIR	Memory-bandwidth-limited throughput, CDKS packing
2023 HintlessPIR	Composable RLWE preprocessing, LinPIR primitive

Group 2a — Download-Hint

Client downloads server-computed global hint. Hint generation is server→client only (one-directional).

Paper	Key Contribution
2026 IncrementalPIR	Entry-level incremental preprocessing for SimplePIR
2024 VeriSimplePIR	Verifiability via SIS commitments + VLHE
2022 FrodoPIR	Plain LWE with client-independent global hint
2022 DoublePIR	Compressed hints via LWE-on-LWE composition
2022 SimplePIR	10 GB/s throughput via plain LWE matrix-vector multiply

Group 2b — Interactive-Hint

Hint generation requires client↔server communication. Only category achieving sublinear online server time.

Paper	Key Contribution
2024 ThorPIR	Client-dependent FHE preprocessing
2024 WangRen	Tight ST = O(nw) tradeoff (theory)
2024 Plinko	Invertible PRFs, Õ(1) updates (theory)
2024 RMS24	Dummy subsets, standard correctness
2023 Piano	First practical sublinear-server, PRF-only

Group X — Extensions

Paper	Key Contribution
2025 DistributionalPIR	Distribution-dependent PIR model + compiler framework
2019 KeywordPIR 1	Comparison of SealPIR, MulPIR, Gentry-Ramzan for keyword PIR

Footnotes

1. The "MulPIR" referenced in KeywordPIR is the Ali et al. [1] implementation of Gentry & Halevi's "Compressible FHE with Applications to PIR" [2], which is already covered under mulpir_2019. Open-source implementations: [3] [4]. ↩