PIR Wednesday — August 12 2026 Weekly Update

What Was Done

New Research Catalogued

Five major papers and two deployment developments discovered since the August 5 update:

1. Henzinger & Ragavan — Two-Server IT-PIR in Sublinear Time (EUROCRYPT 2026). A landmark result: first information-theoretic PIR with quasilinear server storage and polynomially sublinear server time. 4.5 million× smaller preprocessing data structure than prior work.

2. Bitansky & Mazor — Secret-Key PIR from One-Way Functions (ePrint 2026/865). Foundational result: SK-PIR with Õ(√N) communication under minimal assumptions (one-way functions only). Evidence that PIR may not require public-key crypto.

3. Arunachalaramanan, Chen & Ren — PIR Tutorial and Survey (ePrint 2026/1135). Comprehensive UIUC survey covering all major PIR paradigms with concrete efficiency characterization and practical paradigm-selection guidance.

4. Döttling — Minicrypt PIR for Big Batches (ePrint 2025/1406). Two-server batch PIR from Minicrypt assumptions (no public-key required).

5. MDPI — Dynamic Database PIR via Multi-Key FHE (Electronics journal, 2025). PIR scheme supporting collaborative multi-data-owner computation.

Deployment Tracking Updated

6. Oblivious Labs → Kohaku: Ethereum Foundation Q1 2026 allocation confirms funded grant connecting Oblivious Labs server to Kohaku wallet extension for private state reading. First concrete pipeline from PIR/ORAM research to wallet deployment.

7. Kohaku Architecture Clarified: IQ.wiki page reveals Kohaku's initial private state reading uses TEE+ORAM (oblivious server), with PIR as the long-term cryptographic endgame. Privacy-service abstraction is a Phase 1 deliverable.

Key Research Findings (August 2026)

1. Henzinger & Ragavan: Two-Server IT-PIR Breakthrough (EUROCRYPT 2026)

Paper: "Two-Server Private Information Retrieval in Sublinear Time and Quasilinear Space" ePrint: https://eprint.iacr.org/2025/2008 Venue: EUROCRYPT 2026 (DOI: 10.1007/978-3-032-25330-9_3) Authors: Alexandra Henzinger, Seyoon Ragavan (MIT)

This is arguably the most significant information-theoretic PIR result since Beimel, Ishai, and Malkin (CRYPTO 2000). The paper achieves:

Key insight: A compact data structure for evaluating multivariate polynomials and their derivatives. Hasse derivatives can be computed on-the-fly via finite differences between polynomial evaluations.

Significance: This is the first IT-PIR with any constant number of servers achieving quasilinear server storage n^{1+o(1)} AND polynomially sublinear server time n^{1-Ω(1)} simultaneously. Prior IT-PIR schemes required either linear server time or superlinear storage. The result fundamentally changes what is achievable with two non-colluding servers.

Limitation: Large communication complexity (4.4 MB/query on 11 GB DB). The paper shows how to reduce this to n^0.31·poly(λ) using compact linearly homomorphic encryption, but at the cost of moving to computational assumptions.

Also extends: Improves state-of-the-art in PIR with 3+ servers, building on Ghoshal, Li, Ma, Dai, and Shi (TCC 2025).

2. Secret-Key PIR from One-Way Functions (ePrint 2026/865)

Paper: "Secret-Key PIR from One-Way Functions" ePrint: https://eprint.iacr.org/2026/865 Authors: Nir Bitansky, Noam Mazor (NYU)

A foundational result that reshapes our understanding of PIR's cryptographic requirements:

• SK-PIR model: The client processes the database offline using a short secret key. Online queries use the key to privately retrieve entries with sublinear communication o(N).
• Main result: SK-PIR with online communication Õ(√N) from one-way functions alone — the minimal cryptographic assumption.
• Trade-off: Client-to-server communication Õ(N_c) and server-to-client communication Õ(N_s) as long as N_c · N_s ≥ N.
• Construction: Based on garbled circuits with an uncorrelated input encoding property.

Significance: Standard (public-key) PIR requires public-key cryptography. This work shows secret-key PIR can be built from the weakest cryptographic assumption (OWFs). Combined with Chen, Ishai, Mour, and Rosen (STOC 2026) constructing SK-PIR from high-noise LPN, there is growing evidence that SK-PIR is fundamentally easier than public-key PIR.

Relevance to freedom tech: SK-PIR could enable simpler PIR deployments where the client has an offline pre-processing relationship with the server, avoiding the complexity of lattice-based public-key infrastructure.

3. PIR Tutorial and Survey (ePrint 2026/1135)

Paper: "Private Information Retrieval: A Tutorial and Survey" ePrint: https://eprint.iacr.org/2026/1135 Authors: Pranav Shriram Arunachalaramanan, Yue Chen, Ling Ren (UIUC)

A comprehensive survey from Ling Ren's group at Illinois covering: - IT-PIR vs CPIR paradigms - Preprocessing vs stateful PIR - Keyword PIR extensions - Batch PIR - Concrete efficiency comparisons across paradigms - Practical paradigm-selection guidance - Real-world applications

Value: This is the best entry point for newcomers to PIR since the UT Austin tutorial (Wu, June 2024). Covers the 2025–2026 frontier papers and provides decision trees for selecting a PIR scheme in practice.

4. Minicrypt PIR for Big Batches (ePrint 2025/1406)

Paper: "Minicrypt PIR for Big Batches" Authors: Nils Döttling

• Two-server batch PIR from Minicrypt assumptions (no public-key crypto needed).
• Offline/online model where a client retrieves a batch of entries simultaneously.
• Batch amortization brings server-side cost per entry close to single-query cost.
• Cited by 3 subsequent papers.

5. Dynamic Database PIR via Multi-Key FHE (MDPI Electronics, 2025)

Paper: "Efficient Private Information Retrieval Scheme with Dynamic Database" Journal: Electronics (MDPI), 2025 — https://www.mdpi.com/2079-9292/14/17/3441

• Uses Multi-Key FHE (MKFHE) for PIR.
• Supports collaborative computation across multiple data owners without disclosing private information.
• Dynamic database updates via transferable optimization encoding single columns into polynomial ring structures.
• Relevant for real-world multi-party database scenarios.

Kohaku / Ethereum PIR Deployment Update

Oblivious Labs → Kohaku Pipeline (EF Q1 2026 Funding)

The Ethereum Foundation's Q1 2026 allocation report (April 29, 2026) confirms a funded grant:

Privacy | Developer tooling | Oblivious Labs server <> Kohaku — "Builds an Oblivious server to handle requests from the Kohaku extension's embedded execution client, enabling private state reading."

This is the first confirmed pipeline connecting PIR/ORAM research to the Kohaku wallet. Oblivious Labs is building the server component that handles private state queries from Kohaku's browser-based execution client.

Also funded: "Unblocking Tor bridge scalability" — addressing Tor bridge bottlenecks for EF Privacy Team's network-level privacy integration.

Kohaku Architecture — TEE+ORAM Now, PIR Later

The IQ.wiki page for Kohaku clarifies the deployment architecture:

Kohaku's Private State Reading feature works as follows: - A minimal execution client runs in the browser for private eth_call functions. - The initial implementation uses an oblivious server combining TEE + ORAM. - The long-term plan replaces this with purely cryptographic PIR.

Other Kohaku privacy features relevant to PIR: - Helios light client (WASM in browser) for local RPC verification - P2P transaction broadcasting (bypass centralized relayers) - One Account Per dApp (compartmentalize on-chain footprint) - Privacy-service abstraction as Phase 1 deliverable

CryptoSlate Analysis (January 2026)

CryptoSlate's deep dive on Ethereum's 2026 privacy roadmap frames PIR/ORAM as "trajectories and prototypes, rather than something users have today." Key framing:

• Scale challenge: ~33 million leaves ≈ ~1 GB trie. PIR targets KB/query bandwidth with heavy server-side compute.
• Vitalik's progression: TEE (now) → PIR (endgame) for private reads.
• Maturity: Research / early prototypes. Not user-facing yet.
• Privacy-service abstraction: Explicitly listed as a Kohaku Phase 1 deliverable.

Updated Evidence at a Glance — New Papers This Week

Updated PIR Frontier Map (August 12 2026)

The field continues its diversification. Updates to the seven frontier areas from last week:

1. Information-Theoretic PIR Resurgence

NEW this week: The Henzinger/Ragavan EUROCRYPT 2026 paper fundamentally changes the IT-PIR landscape. For 25 years, IT-PIR (Beimel-Ishai-Malkin 2000 and successors) required either linear server time or exponentially large storage. Now: quasilinear storage (n^{1+o(1)}) with polynomially sublinear time (n^{1-Ω(1)}) is achievable with just 2 servers. This is a paradigm-shifting result that reopens the two-server deployment path.

Combined with Döttling's Minicrypt batch PIR, the two-server paradigm is seeing its strongest advances since the early 2000s.

2. Foundational Theory — PIR's Cryptographic Requirements

NEW this week: Bitansky & Mazor's SK-PIR from OWFs (2026/865) plus Chen et al.'s SK-PIR from LPN (STOC 2026) reveal a fundamental split: - Public-key PIR (standard CPIR): Requires lattice/DDH assumptions. The dominant practical paradigm. - Secret-key PIR: Requires only one-way functions (or even high-noise LPN). Easier to construct but requires client-server pre-processing relationship.

This has implications for deployment: SK-PIR may be sufficient for scenarios where the client has an established relationship with the server (e.g., wallet ↔ RPC provider with a pre-processing phase).

3. Incremental / Dynamic Databases

Still led by iSimplePIR (entry-level updates), Conflux (keyword PIR for dynamic data), PIRacle (key-value stores). The MKFHE dynamic PIR paper adds a multi-owner dimension.

4. Keyword PIR

KPIR (USENIX Sec 2025), Conflux (HPCA 2026), ChalametPIR remain the leaders. No new entries this week.

5. Verifiability

VeriSimplePIR, "Verifiable PIR with Small Client Storage" (S&P 2026). No new entries.

6. Hardware Acceleration

GPIR (GPU), SmartPIR (CSDs), IM-PIR (PIM), IVE (custom ASIC, Kim et al. 2026). The IVE architecture proposes a custom accelerator with large on-chip scratchpads and tightly scheduled execution for multi-client batched PIR — a signal that PIR is being considered for silicon-level optimization.

7. Ethereum Integration

Major update: Oblivious Labs → Kohaku pipeline confirmed via EF Q1 2026 funding. Kohaku's architecture clarifies the TEE+ORAM → PIR progression. Privacy-service abstraction is a Phase 1 deliverable.

Updated Survey Resources