PIR Wednesday — September 16 2026 Weekly Update

The seven-day window between the September 9 and September 16 sweeps saw four new ePrint papers spanning the full PIR stack: a foundational lower bound (Keewoo Lee / Ethereum Foundation lifts the 20-year IT-2-server bound from 5·log n to (6−o(1))·log n), a 2× throughput improvement on InsPIRe (ReinsPIRe, Google / Columbia / Waterloo), a new silent-preprocessing PIR based on NTRU rather than RLWE (NTPIR, Ant Group, CCS 2026 accepted), and a DNS-tailored single-server PIR that outperforms all previous schemes on communication (DNSPIR, RHUL / NTNU, PoPETS'27 accepted). SandwichPIR repo remains static at 2 stars with no new commits since the Aug 28 ePrint snapshot; the new Keewoo Lee lower bound is the clearest signal that the canonical IT-2-server construction has been formally closed for nearly three decades of tightening attempts and that further deployment wins must come from the single-server LWE/FHE side.

TL;DR

1. IT-2-server PIR communication lower bound: 5 → 6 — ePrint 2026/1959, submitted 2026-09-10, approved 2026-09-13. Keewoo Lee (Ethereum Foundation), Berkeley PhD and VeriSimplePIR (S&P 2026) co-author. The bound lifts Wehner–de Wolf (ICALP 2005) from 5·log n to (6−o(1))·log n. Proof follows the quantum route but with a sharper readout: real-valued outcome whose mean is the correct answer instead of a binary outcome with small bias toward correct; pays only the second moment instead of the inverse square of the bias. The same technique drops the linearity assumption in the Goldreich–Karloff–Schulman–Trevisan (CCC 2002) bounds "almost for free". This is a foundational tightening — the 5·log n bound has stood since 2005; every 2-server PIR construction is now formally below the optimum by at least one full log factor.
2. ReinsPIRe: 2× throughput over InsPIRe (S&P 2026) — ePrint 2026/1934, submitted 2026-09-08. Mahdavi / Patel / Seo / Yeo (Google, Columbia, Waterloo) — same team as InsPIRe. 5.9 GB/s/server-core throughput (2× InsPIRe), achieved by letting most server FHE ops avoid NTT polynomial encodings entirely (moduli natively supported by modern hardware, smaller cryptographic material). Two applications packaged: (a) in-storage PIR with external SSD — 3.3× better throughput; (b) vReinsPIRe verifiable PIR — smallest online communication cost + ~50× smaller long-term client storage vs prior low-comm verifiable PIR (VeriSimplePIR / UC VPIR). The most consequential single-server PIR throughput result since InsPIRe's own publication, and it lands 5 months later in the same author's stack.
3. NTPIR: silent-preprocessing PIR on NTRU — ePrint 2026/1910, submitted 2026-09-07, accepted CCS 2026 (DOI 10.1145/3830454.3846680). Zhihao Li / Cheng Hong (Ant Group). Three new techniques: (1) Pack-then-switch — ring packing in RLWE domain, single key switch to NTRU, yielding single-element packed intermediates (vs RLWE ring packing as the bottleneck in prior silent-preprocessing PIR); (2) Split-point picking — collapses automorphism complexity from linear to √N; (3) FFT-based polynomial mult + approximate gadget decomposition with concrete correctness error ≤ 2⁻⁴⁰. Up to 1.81× server-side online speedup vs InsPIRe⁽²⁾ (S&P'26) on 1–8 GB databases; 7–41× faster preprocessing at 8 GB. At highest-throughput config: 8,609 MB/s on 8 GB = 1.38× InsPIRe⁽²⁾, 1.8× SimpleYPIR, 2.0× HintlessPIR. First high-throughput PIR to make NTRU competitive with RLWE for the silent-preprocessing pipeline. The trade-off: NTRU lacks RLWE's public-randomness component, which the Pack-then-switch technique recovers.
4. DNSPIR: PIR optimized for private DNS — ePrint 2026/1872, submitted 2026-09-02, accepted PoPETS'27 (minor revision). Lea Nürnberger / Simon Pohmann / Mattia Veroni / Christian Weinert (RHUL + NTNU). New RLWE-based matrix-vector multiplication algorithm: no NTT-friendly plaintext moduli required, single key-switching key, significantly lower noise growth. On a 2-billion-entry database (≈ all domains worldwide): ~80 KB communication per query, <5 s server computation — outperforms all prior PIR on communication cost (only slightly increased runtime). End-to-end iterative DNS across three nameservers: sub-second lookups in small settings; 264 KB total for a full .com resolution, <5 s — practical for selective use during privacy-sensitive browsing. First PIR with comm cost below 100 KB at 2⁹-entry scale; bridges the gap between research PIR and a DoH/QNAME-minimisation-style deployment.
5. SandwichPIR repo: static — sidsabh/sandwichpir still at 2 stars, 2 commits total, last eprint commit 2026-08-28. No commits in the window, 19 days since the Aug 28 reference commit, 17 days since the Aug 26 release commit. The reference implementation is mature (matches paper numbers; rodeo L40S tensor-core backend; wikipedia/ artifact; full Sweep.py harness) but adoption is glacially slow — the repo isn't trending in any aggregator and hasn't attracted external forks or issues. The Sep 9 sweep flagged 2 stars and Sep 16 confirms it hasn't moved. Compare OpenMined/PIR at 46 stars, 11 watchers (stale but better-known); vectorized_batchpir at 13 stars. SandwichPIR's low visibility despite being the highest-impact PIR paper of 2026 is a real adoption problem for the GPU-PIR niche — likely because the hardware dependency (CUDA 12.4 + L40S) is a deployment moat.
6. Kohaku: 401 stars (up from ~395 across the window), 81 forks, no PIR-tagged PRs in the search filter (the Sep 2 sweep's PR #271 anon-rpc provider backend remains the most recent PIR-adjacent wire-up). Repo is now at 215 commits on master, with the dominant activity being PQ-account, Railgun / 4337 mempool integration, and wallet-SDK plumbing per the Sep 13 identity sweep. The PIR layer in Kohaku remains TEE+ORAM, with PIR as the longer-term target — consistent with the HackMD roadmap and Vitalik's 2026 privacy-roadmap framing in the Sep 11 Cryptoslate piece.

Lead Story — Keewoo Lee Closes a 20-Year Lower-Bound Hunt

||Paper: Information-theoretic two-server PIR requires (6−o(1))·log n bits of communication | ||Author: Keewoo Lee, Ethereum Foundation (Berkeley PhD 2024) | ||Submitted: 2026-09-10 | ||Approved: 2026-09-13 | ||ePrint ID: 2026/1959 | ||Category: Foundations | ||Category note: this is the only Foundations-tagged PIR paper of the cycle — every other Sept submission is in Cryptographic Protocols or Applications |

Why the bound matters concretely: every information-theoretic 2-server PIR scheme to date (Chor–Gilboa–Naor, Beimel–Ishai–Malkin CRYPTO 2000, Dvir–Gopi JACM 2016, Henzinger–Ragavan EUROCRYPT 2026 sublinear-time, the Beimel–Ishai line on preprocessing) is at least one full log factor away from the new bound, even though Dvir–Gopi's O(n^{1/3}) scheme is asymptotically tight up to constants. The Lee bound raises the bar on information-theoretic communication; it does not affect the computational LWE/FHE-based single-server family (ReinsPIRe, NTPIR, InsPIRe, YPIR, SimplePIR), which doesn't approach log n communication in any case.

The trick (compact): prior quantum-route proofs encoded the database in a quantum state, read out a binary outcome with small bias toward the correct answer, and amplified. Lee lets the outcome be real-valued with mean equal to the correct answer; amplification now pays only the second moment, not the inverse square of the bias. The same readout also drops the linearity assumption in Goldreich–Karloff–Schulman–Trevisan (CCC 2002) "almost for free".

Why this is structurally important: the lower-bound community has been trying to close this gap since 2005. The Henzinger–Ragavan EUROCRYPT 2026 construction (Aug 5 sweep) achieves n^{1−Ω(1)} server time but communication is n^{0.31}·poly(λ) — still super-logarithmic. The new Lee bound says: no IT-2-server scheme can do better than 6·log n communication. So either (a) you accept computational hardness (LWE/RLWE/NTRU/Ring-LPN) and break the IT-PIR ceiling, or (b) you accept IT-PIR but pay O(n^{1/3}) (Dvir–Gopi) or worse communication. The choice is fundamental to deployment architecture.

Keewoo Lee's track record (Berkeley CV): - VeriSimplePIR (S&P 2026) — verifiable PIR with small client storage, Mayank Rathee + Raluca Ada Popa - USENIX Security 2026 — Bypassing Prompt Guards in Production (with Fairoze / Garg / Wang) - EDCON 2024 — Oblivious Message Retrieval for ZCash - MPC & FHE Residency at PSE Team (Ethereum Foundation), Tokyo, Jul 2024 - Currently Ethereum Foundation (contact email: keewoo.lee@ethereum.org)

The Ethereum Foundation affiliation is the deployment tell: VeriSimplePIR is the small-client-storage PIR that Kohaku has been positioned to use; Lee's lower-bound work tightens the IT-2-server ceiling that Kohaku's "use two non-colluding Helios light clients" pattern would hit. The Foundation is mapping the deployment envelope from both sides: how low can IT-2-server go (answer: 6 log n), and how low can single-server computational go (ReinsPIRe / NTPIR / SandwichPIR race).

Story 2 — ReinsPIRe Doubles InsPIRe Throughput, Adds Verifiable Variant

||Paper: ReinsPIRe: High-Throughput, Low-Communication PIR with Server Preprocessing | ||Authors: Rasoul Akhavan Mahdavi (Google / Waterloo), Sarvar Patel (Google), Joon Young Seo (Google), Kevin Yeo (Google / Columbia) | ||Submitted: 2026-09-08 | ||ePrint ID: 2026/1934 | ||Category: Cryptographic protocols |

The ReinsPIRe–InsPIRe pipeline (same team, 5 months apart) is now the dominant single-server PIR stack on Google Cloud:

The architectural win: prior InsPIRe/FHE-PIR schemes encode everything via NTT polynomial representation. ReinsPIRe lets most server-side operations run as plain matrix multiplication on hardware-native moduli — no NTT round-trips. The polynomial mult for the small remaining operations still uses matrix multiplication. Result: drastically smaller memory bandwidth pressure + 2× throughput. This is the same family of engineering wins that SandwichPIR rodeo and YPIR SimplePIR/FHE pipelines already exploit; ReinsPIRe applies them to the CRS-model preprocessing family that InsPIRe pioneered.

vReinsPIRe: ReinsPIRe also ships a verifiable variant. Smallest online communication cost among verifiable PIRs + ~50× smaller long-term client storage vs prior low-comm verifiable PIR. Comparable to VeriSimplePIR (S&P 2026, Rathee/Lee/Popa) on comm; much smaller storage footprint.**

The in-storage PIR variant: when the database is too large for RAM and lives on SSD, 3.3× better throughput than prior work because the smaller cryptographic material reduces the per-query I/O. Realistic for ≥ 100 GB databases where in-memory PIR is impractical.

Deployment picture: ReinsPIRe lands 5 months after InsPIRe (S&P 2026) and explicitly improves it. It does not supersede SandwichPIR (which is the GPU-tensor-core extreme) or YPIR (the highest-throughput absolute); it sits in the CPU high-throughput + small comm + server-side preprocessing niche alongside InsPIRe and 2× ahead of it.

Story 3 — NTPIR: First High-Throughput Silent-Preprocessing PIR on NTRU

||Paper: NTPIR: Efficient Silent-Preprocessing PIR using NTR | ||Authors: Zhihao Li, Cheng Hong (Ant Group) | ||Submitted: 2026-09-07 | ||ePrint ID: 2026/1910 | ||Category: Applications | ||Publication info: Accepted at CCS 2026 (DOI 10.1145/3830454.3846680) |

NTPIR addresses the silicon-level question: can you replace RLWE with NTRU in the silent-preprocessing pipeline without losing throughput?

NTPIR's contribution is the Pack-then-switch technique: ring packing happens in the RLWE domain, then one key switch translates to NTRU. The single key switch costs less than the RLWE public-randomness overhead. Result: single-element packed intermediates + NTRU's natural compactness + split-point picking to fold second-layer column selection into response packing.

Numbers (8 GB database, highest-throughput config): - 8,609 MB/s server throughput - 1.38× InsPIRe⁽²⁾, 1.8× SimpleYPIR, 2.0× HintlessPIR - 7–41× faster preprocessing than InsPIRe⁽²⁾ - Up to 1.81× online speedup vs InsPIRe⁽²⁾ - Concrete correctness error ≤ 2⁻⁴⁰

Split-point picking is the second independent contribution: instead of performing automorphisms per packed second-layer input (linear complexity), split-point picking integrates the selection with the packing (√N complexity). This is the structural change; the NTRU switch is the engineering change.

Why Ant Group cares: Cheng Hong is the Director of Cryptography and Privacy Research at Ant Group; Ant Group has been the dominant industrial deployer of LWE/RLWE-based PIR-style primitives for Antchain private transactions (and Alipay privacy-preserving computation since the Alibaba Gemini Lab era). NTPIR's CCS 2026 acceptance is the clearest signal yet that NTRU-based PIR will enter production deployment in a Chinese fintech stack within 12 months.

Architectural position: NTPIR's headline throughput (8.6 GB/s) is below YPIR's 12.1 GB/s/core on 32 GB but above InsPIRe⁽²⁾ at smaller databases. The NTRU ciphertext compactness makes NTPIR preferable for network-bandwidth-bound deployments; the absolute throughput makes it competitive with compute-bound InsPIRe⁽²⁾.

Story 4 — DNSPIR: First PIR With <100 KB Comm at 2 Billion Entries

||Paper: DNSPIR: Private Information Retrieval Optimized for Privacy-Preserving DNS Lookups | ||Authors: Lea Nürnberger, Simon Pohmann (RHUL), Mattia Veroni (NTNU), Christian Weinert (RHUL) | ||Submitted: 2026-09-02 | ||ePrint ID: 2026/1872 | ||Category: Cryptographic protocols | ||Publication info: Accepted at PoPETS'27 (minor revision) |

DNSPIR is the first PIR paper to take the specific workload of DNS resolution and tailor the matrix-vector multiplication algorithm to it. The DNS workload has unusual properties: small record size (~1 KB for most answers, even with DNSSEC/NSEC), very large database (2 billion+ entries — the entire authoritative zone), and iterative resolution across multiple nameservers (root → TLD → authoritative).

Key technical contributions: - New RLWE-based matrix-vector multiplication algorithm that does not require NTT-friendly plaintext moduli (the constraint that bounded NTTlessPIR, InsPIRe, and ReinsPIRe). - Single key-switching key instead of multiple (lower noise growth, smaller material). - Significantly lower noise growth than prior RLWE matrix-vector mult methods.

End-to-end numbers: - Single 2-billion-entry database: ~80 KB comm per query, <5 s server computation. - Outperforms all prior PIR on communication at this scale (vs ReinsPIRe / NTPIR / InsPIRe / SimplePIR / YPIR — all of which are in the 100s of KB to MB range for comparable DB sizes). - Slightly increased runtime vs the fastest schemes — DNSPIR trades ~2× server compute for ~10× comm reduction. - Iterative DNS across 3 nameservers: <5 s, 264 KB total for resolving a .com domain; sub-second for smaller zones.

Deployment realism: "Practical when used selectively for privacy-sensitive browsing activities" is the authors' framing. The 264 KB / 5 s budget is impractical for every DNS query but reasonable for selective resolution of sensitive names (e.g. resolving Tor hidden-service descriptors, fetching DNSSEC-signed zone cuts for certificate transparency). This is the first cryptographic-private-DNS scheme that competes with the QNAME-minimisation / DoH3 ( Oblivious DoH over Tor) approach on communication, with much stronger privacy guarantees (the server doesn't learn the queried name).

Why RHUL/NYT (the Weinert group) matters: Christian Weinert co-authored OPPW25 (Okada–Player–Pohmann–Weinert, EUROCRYPT 2025) on algebraic homomorphic encryption for doubly-efficient PIR. The Fheanor library (ePrint 2025/864) is the same group's work — DNSPIR likely uses an early version. The lineage is "doubly-efficient PIR → FHE library optimized for algebraic HE → PIR optimized for DNS" — a textbook example of a research line maturing into deployment-shape artifacts.

Position vs existing private-DNS work: - Tor + DoH: network-layer privacy, server sees queries in plaintext - Oblivious DoH (ODoH, Oblivious DoH over Tor): hides client IP from DoH server, server sees query in plaintext - Query minimization (QNAME minimization): reduces info per query but server still sees the suffix - DNSPIR: server sees nothing about the queried name — strongest privacy, first scheme with comm under 100 KB

Story 5 — Ecosystem Staleness / Velocity Check

The aggregate picture: the research frontier is moving fast (4 ePrint papers, 1 lower bound, 1 throughput doubling, 1 NTRU-based scheme, 1 DNS-specialized scheme, all in 7 days). The deployment frontier is glacial — SandwichPIR, hintless_pir, OpenMined/PIR, vectorized_batchpir, swift-homomorphic-encryption all show zero activity. The pipeline from "paper → reference implementation → forkable artifact → production" is still ~24 months for LWE-PIR, and the only project actively closing that gap is Kohaku, which is using TEE+ORAM (not PIR) for production and tracking PIR for the next-generation roadmap.

Connections to Other Vault Sections

• Decentralized DNS — DNSPIR is the first PIR paper whose primary deployment motivation is private DNS resolution; sits orthogonally to Overview - Decentralized DNS, ENS, pkarr, and Handshake. The Aug 31 DNS sweep covered the consensus-layer alternatives; DNSPIR covers the access-pattern layer (resolver↔authoritative).
• Decentralized Compute — ReinsPIRe and SandwichPIR both target the GPU-accelerated / high-throughput compute server deployment model that Decentralized Compute tracks via Phala, Aethir, Akash, io.net. The Ant Group NTPIR result is the first NTRU-based PIR — NTRU lattice hardness assumptions overlap with the Post-Quantum migration story; Ant Group has been a major contributor to PQ-NIST submissions.
• Confidential Computing — ReinsPIRe / InsPIRe / NTPIR / SandwichPIR all push single-server PIR toward production economics; TEE+ORAM (Intel SGX, AMD SEV, NVIDIA H100) is the only currently shipping private-reads layer in Kohaku. The two are complementary: TEE provides hardware-rooted attestation; PIR provides cryptographic access-pattern hiding even against a malicious TEE vendor.
• Identity & Pseudonymity — Keewoo Lee's Ethereum Foundation affiliation + VeriSimplePIR (S&P 2026) + this lower bound means the Ethereum Foundation is mapping the PIR deployment envelope from the foundation up. Identity (Nostr, NIP-85, Identity Sunday Sept 13) and PIR converge on the wallet/private-reads surface — both are needed for pseudonymous blockchain interaction.
• Zero-Knowledge — ZK proofs (Groth16, PLONK, STARK) and PIR are the two complementary building blocks for cryptographic access-pattern hiding in client-server protocols. The Aug 5 PIR sweep catalogued the SK-PIR toolbox exports to encrypted matrix-vector products — same family of primitives.

Evidence at a Glance

Filing Notes

• Topic: PIR (Private Information Retrieval) — Wednesday rotation, week of Sep 14–20, 2026
• Cross-section touch: Decentralized DNS (DNSPIR), Post-Quantum (NTRU lineage), Decentralized Compute (high-throughput server deployment), Confidential Computing (TEE+ORAM vs PIR deployment race), Identity (Kohaku/Ethereum Foundation pipeline)
• Source papers catalogued: 4 new (2026/1959, 2026/1934, 2026/1910, 2026/1872)
• Repositories re-verified: 6 (SandwichPIR, Kohaku, OpenMined/PIR, vectorized_batchpir, google/private-retrieval, google/hintless_pir)
• Adjacent news: Identity Sunday Sept 13 (Kohaku star growth, PQ-account, NIP-42), Post-Quantum Saturday (NTRU lattice assumptions overlap)