PIR Wednesday — September 2 2026 Weekly Update

TL;DR

1. SandwichPIR (Sabhnani–Wu, ePrint 2026/1816, Aug 28 2026): first single-server PIR to cast the bulk of server computation as 8-bit integer matrix multiplications on GPU tensor cores; 8.2 ms/query on a 4 GB / 32 KB-record database (488 GB/s server throughput — 88× the best no-offline CPU protocol); batched throughput climbs to 24 TB/s single-GPU, 270 TB/s 8-GPU fleet; private Wikipedia retrieval (8 GB compressed) at <200 ms end-to-end, 768 KB query, $0.20 / million queries on AWS — the first time a single-server PIR cost estimate is competitive with rate-limited unauthenticated web scraping.
2. Atom (Li–Xiang–Yang–Yu–Zhou, ePrint 2026/1813, Aug 28 2026, same Shanghai group as LetoPIR): single-server PIR with 0.4–5.0 s query time AND 3.0–3.8 KB online communication for 256 B records over 256 MB–8 GB databases — 40.5–51.3× online-comm reduction vs KsPIR (CCS'24) at parity running time. Atom collapses the historical "low-comm but slow" vs "fast but big" PIR trilemma to "low-comm and fast."
3. LetoPIR (Li–Yang–Liu–Xiang–Zhou–Xie–Yu, ePrint 2026/1814, Aug 28 2026): hintless keyword PIR with logarithmic communication; 12.4–17.0× comm improvement vs SparsePIR (USENIX'23) and 51.4–184.8× vs KPIR (USENIX'25) at similar or better compute. Powered by efficient FHE k-hot-vector generation + a bucket-merging technique — both plausibly general purpose.
4. Kohaku Sep 1 commit (no release yet): PR #276 — "Add external sync provider to railgun + subsquid toggle for local dev." 402 stars (+3 since Aug 26). No PIR/ORAM read-path artifact, but the week-over-week traffic and the SP1 v6 zk-proofs pivot from the Aug 21 release keep the roadmap thread alive.
5. Repo watch snapshot: apple/swift-homomorphic-encryption 657 stars (+2) — last push Aug 31 (vendor bump, no new release); google/hintless_pir 23 stars, last push Jul 23 — the staleness now exceeds 5 weeks, but the implementation remains the only public hintless LWE-PIR reference.

Lead Story — SandwichPIR: Single-Server PIR Hits 8 ms per Query

Paper: "From Lattices to Tensor Cores: Accelerating Private Information Retrieval" Authors: Sidaarth Sabhnani (UT Austin), David J. Wu (UT Austin) ePrint: https://eprint.iacr.org/2026/1816 (Aug 28 2026) Slides (Wu, Austin, Aug 2026): https://www.cs.utexas.edu/~dwu4/talks/SandwichPIR0826.pdf Author page: https://www.sidsabhnani.com

The single-server PIR throughput ceiling has been GPU-shaped for two years (TCHES 2026 GPU DPF-PIR pushed published CPU single-server to ~8× speedup, then SmartPIR/IVE followed). SandwichPIR is the first single-server scheme to reformulate the entire server polynomial evaluation as a single dense 8-bit integer matmul on GPU tensor cores — the same hardware primitive that powers LLM training. The protocol requires no offline communication between client and server (unlike YPIR or Spiral); the client uploads only the index hint.

Headline numbers (L40S, single query, no batch):

Comparison: 88× the best no-offline CPU PIR baseline. For batched queries (128 clients, same database): 0.16 ms / query (24 TB/s), and 270 TB/s effective throughput with an 8-GPU fleet over a 256 GB database (119 ms per batch). The GPU moves PIR from "memory-bandwidth-bound server" to "compute-bound server that can scale with the GPU fleet you can afford."

Deployment anchor: end-to-end private access to (text-only) English Wikipedia (8 GB compressed). An article up to 128 KB retrieved in 768 KB of client-server communication and <200 ms end-to-end over broadband — single-GPU sustained throughput of 2,500 queries/sec at $0.20 per million queries on AWS L40S. This is the single most consequential deployment number in this library: it makes a single-server public-good database (Wikipedia) plausibly servable under PIR at retail web-API cost economics.

What makes the breakthrough structural, not engineering: - The "tensor cores eat dense 8-bit matmul" trick generalizes: any LWE-PIR scheme whose evaluation is dominated by a single matrix-vector product (SimplePIR-family, HintlessPIR, Spiral-family) can be re-expressed under SandwichPIR's protocol. The matmul is the new universal inner-loop primitive, displacing NTT-based polynomial multiplication. - No offline communication means the "PIR-with-hints" deployment pipeline (which requires either a per-client hint compute or a YPIR silent-setup phase) collapses: the only offline cost is the one-time per-database secret hint that the server stores in plain. - The 8.2 ms ceiling is compute-bound, not memory-bound — Scaling to a larger database (256 GB) is a function of how many GPUs you have, not a function of matmul dimension growth.

Why it was missed by the Aug 19 and Aug 26 sweeps: the ePrint batch landed Aug 28 2026 (within 48 hours of the Aug 26 update commit). The author's talk slides date to Aug 2026 (filename SandwichPIR0826.pdf) — likely a departmental or venue preview.

Atom — The PIR Trilemma Collapses for Indexed Retrieval

Paper: "Atom: Single-Server Private Information Retrieval with Low Communication and Fast Computation" Authors: Baoyu Li, Binwu Xiang, Kang Yang, Qi Liu (or Yang?), Xiaogang Zhou — the Shanghai Jiao Tong / East China Normal group that also authored LetoPIR ePrint: https://eprint.iacr.org/2026/1813 (Aug 28 2026)

Prior single-server PIR protocols with database-independent preprocessing split into two camps: - Low communication (KsPIR, CCS'24): tens of KB → sub-KB online comm, but seconds-to-tens-of-seconds query time. - Fast computation (YPIR and successors): sub-second query time, but online comm in hundreds of KB.

Atom takes 3.0–3.8 KB online communication AND 0.4–5.0 s query time for 256 B records over 256 MB to 8 GB. Against KsPIR (CCS'24) at parity running time, Atom reduces online communication 40.5–51.3×.

Why the trilemma collapsed: the underlying database-independent preprocessing generates a relatively compact hint from which the per-query matmul remains small. The combination of (a) lower database-dependent overhead at hint generation and (b) smaller per-query ciphertext size lets Atom win on both axes simultaneously. Detailed construction is in the ePrint; the result is the paper's headline.

Where Atom fits relative to SandwichPIR: Atom is CPU-friendly (no GPU tensor cores required, deployable on commodity cloud VMs) and beats KsPIR on comm; SandwichPIR is GPU-optimized and beats everything else on raw latency. The two papers partition the deployment surface: - Commodity deployments (any VPS, no specialized hardware): Atom is the new frontier. - GPU-backed deployments (Wikipedia-scale public-good database, private analytics on TB-scale data lakes): SandwichPIR.

Neither paper makes the other's deployment obsolete — Atom's cost-per-million-queries on commodity hardware is roughly 100× higher than SandwichPIR on AWS L40S ($20 vs $0.20), but its capital expenditure is also 100× lower.

LetoPIR — Hintless Keyword PIR at Logarithmic Communication

Paper: "LetoPIR: Fast Keyword Private Information Retrieval with Logarithmic Communication" Authors: Baoyu Li, Kang Yang, Qi Liu, Binwu Xiang, Xiaogang Zhou, Xiang Xie, Yu Yu (same group as Atom) ePrint: https://eprint.iacr.org/2026/1814 (Aug 28 2026)

Keyword PIR (kPIR) lets the client retrieve "the record whose key field equals X" without revealing X. State-of-the-art as of August 2026 split cleanly: - With client hint (KPIR, USENIX'25): logarithmic comm, but requires per-client preprocessed state. - Hintless (SparsePIR, USENIX'23): no hint needed, but practical comm was O(√n) with a large constant — prohibitive at TB scale.

LetoPIR achieves logarithmic online comm in the hintless setting. Two technical ingredients: 1. FHE-based k-hot-vector generation: efficiently produce an encrypted query vector with exactly k non-zero components — the data structure that says "I want the record whose key matches any of these k bucket positions." 2. Bucket-merging: reduces the maximum bucket size in the database, preventing the worst-case ciphertext blowup that plagued prior hintless schemes.

Numbers: 12.4–17.0× comm reduction vs SparsePIR at 256 MB–4 GB databases with 256 B records; 51.4–184.8× comm reduction vs KPIR (hintful) at similar or better compute. For a database you'd want to query by keyword — DNS over PIR, contact-discovery, encrypted search at scale — LetoPIR is now the throughput frontier without the deployment burden of client-side hint state.

Sub-techniques are independently interesting: - The k-hot-vector-in-FHE technique generalizes to any "oblivious keyword query" construction — including possibly encrypted email search, private contact discovery, and (relevant to Nostr) private DVM search. - The bucket-merging technique is a generic optimization for any keyword-PIR scheme whose ciphertext expansion depends on bucket size — applies as a drop-in to Conflux (SOSP 2024) and to follow-ups.

Code Availability — All Three Are Paper-Only at This Stage

Recon checks (Sep 2 2026):

Until the code drops, the prior watch list (apple/swift-homomorphic-encryption at 657★, pushed Aug 31 vendor bump; google/hintless_pir at 23★, pushed Jul 23 — the only public hintless LWE-PIR reference; HintlessPIR-derived Python bindings) remains the best path for practitioners experimenting with these new constructions.

Frontier Map Updates (since Aug 26)

1. Single-server PIR rate-limit: prior ceiling was ~8× CPU speedup (TCHES 2026 GPU DPF-PIR); SandwichPIR pushes it 88× CPU no-offline on a single L40S — 11× over the prior GPU best. Atom closes the comm-compute trade-off for indexed retrieval without GPU. The "PIR is too slow to deploy" argument is now structurally retired for any workload that can fit a GPU.
2. Keyword PIR hits log-comm without hint: LetoPIR retires the KPIR-vs-SparsePIR trade-off — you no longer pay either a per-client hint burden OR quadratic-comm overhead. Private contact discovery, private DVM search, and private DNS-over-PIR become shippable without bespoke hint infrastructure.
3. The Shanghai group's publishing cadence: three ePrints in 48 hours (1813, 1814, 1815+; 1815 is the unrelated SMT paper). Atom and LetoPIR share authors and presentation cadence — expect an integrated construction or a combined follow-up within ~3 months.
4. GPU-PIR ready for production-economics pilot: the $0.20 / million-queries number converts private-Wikipedia, private-OpenStreetMap, and other public-good databases from "architectural curiosity" to "pilot-able within an existing AWS budget." Any team piloting should test against SandwichPIR with a single A100/L40S node before committing to a custom CPIR-with-preprocessing stack.
5. Ethereum: Kohaku Sep 1 commit (PR #276, 27995dd) is the only material movement since Aug 26 — adds external sync provider to Railgun + Subsquid toggle for local dev. The private-reads milestone remains un-shipped; the new provider package from Aug 21 is the closest signal we have for a future read-path surface.

Evidence at a Glance — New This Window

Watchlist — Next 7–14 Days

• SandwichPIR, Atom, LetoPIR code releases: all three are paper-only Sep 2; vendor-group cadence (Wu, Li/Yu) suggests 4–8 week horizon. Track author GitHub for first commit.
• IETF / standards adoption of GPU-PIR: the $0.20 / million-queries economics are now competitive with Public Suffix List + DNSSEC + Tor-certificate-transparency audits — a real-world deployment study (e.g., a Wikipedia mirror deployed behind SandwichPIR for censorship resistance) would be the missing piece to convert any cautious holdout.
• Kohaku post-roadmap release: the Jan–Aug "Abstraction Core with Privacy by Design" window formally closed Aug 31. First release after that with any read, state, or or am keyword is the section's first wallet-visible PIR artifact.
• ePrint follow-up thread to 2026/1780 (t-private share conversion wall): theoretical response expected from the Beimel–Lasri–Alon camp. If a constructive t-private share conversion is found, it would re-open the matching-vector IT-PIR line — otherwise the wall is permanent.
• Apple swift-homomorphic-encryption release: iOS 26 cadence typically ships with a new major release each September; any release with new PIR primitives would carry Live-Caller-ID-class news. Repository idle since Aug 31 (vendor bump only).
• CRYPTO 2026 accepted papers (Aug 17–20 proceedings): still no clean extraction; expected venues (CRYPTO 2027 / TCC 2026) for the negative results and the LPN-PIR line.