ungovernable.tech
search 245 entries/ctrl k

Briefing · PIR Wednesday

PIR Wednesday — August 26 2026 Weekly Update

published 2026-08-26 8 min read Privacy-Enhancing Cryptography

TL;DR

  1. Bar Alon, "The Limits of t-Private Share Conversion" (ePrint 2026/1780, Aug 23) proves there is no t-private share conversion from Z_m to F_q for t ≥ 2 (q coprime to m). The Alon–Beimel–Lasri (TCC 2025) framework — the abstraction underlying the modern matching-vector IT-PIR line — cannot be instantiated to yield t-private PIR. Second negative result in two weeks for the IT-PIR camp, after the arithmetic-PIR impossibility of Aug 19.
  2. Applebaum–Shechter, "Retrieve-Compute PIR and Its Applications" (ePrint 2026/1372, revised Aug 9 — missed by the Aug 19 sweep): a two-server PIR variant where the second server is a retrieval-only static-content host doing zero PIR-specific computation — grounding non-collusion in realistic deployment (CDN/repo hosting) rather than "two honest cryptographers." From ternary LPN with inverse-polynomial noise: k-server PIR, robust PIR for arbitrary monotone access structures, and k-party secure lookup-table computation — none previously known under LPN.
  3. Encrypted Matrix-Vector Products from secret dual codes (ePrint 2025/858, revised Aug 24): Benhamouda, Chen, Halevi, Ishai, Krawczyk, Mour, Rabin, Rosen. The SK-PIR permuted-code toolbox (same lineage as benchmarked SK-PIR 2026/1480) generalized to repeated encrypted M·q products under LPN/LSN — online cost <2× computing M·q in the clear. The secret-key PIR line is now an export engine for secure ML and encrypted fuzzy search.
  4. OKVS fortnight: Multi-PGBF (ePrint 2026/1774) — 65–78% faster encoding than RR (CCS'22), ~90–96% faster decoding than RB-OKVS; updatable multi-party PSI via FSS+OKVS with one-pass online rounds (ePrint 2026/1772). Combined with UOKVS (2026/1590, Aug 12 update), the OKVS substrate is the most active PIR-adjacent data-structure frontier of August.
  5. Kohaku release batch Aug 21 (GitHub-verified): all plugins bumped — railgun alpha.30, tornado-cash alpha.21, privacy-pools alpha.16, plugins .13 — plus a new package: @kohaku-eth/provider@0.1.0-alpha.9. 399 stars. Includes a UTXO-drain fix on checksummed token addresses. Still private-writes only; no PIR/ORAM read path has landed.

Lead Story — The Share-Conversion Ceiling for t-Private IT-PIR (ePrint 2026/1780)

Paper: "The Limits of $t$-Private Share Conversion" Author: Bar Alon (single-author) ePrint: https://eprint.iacr.org/2026/1780 (received Aug 23 2026)

The state-of-the-art information-theoretic PIR protocols — Efremenko (SICOMP 2012), Dvir–Gopi (STOC 2015), Ghasemi–Kopparty–Sudan (STOC 2025) — all combine matching vectors over Z_m with decoding polynomials over F_q. Beimel–Ishai–Kushilevitz–Orlov (CCC 2012) abstracted the decoding-polynomial step as share conversion (parties locally convert a Z_m-sharing into an F_q-sharing); Alon–Beimel–Lasri (TCC 2025) rebuilt the modern protocols on this abstraction.

Alon observes that if the conversion starts from a t-private secret-sharing scheme, the resulting PIR inherits t-privacy (no set of t servers learns the index) — and would potentially beat the best known t-private PIR bounds (Woodruff–Yekhanin CCC 2005; Barkol–Ishai–Weinreb 2007). The natural question: do t-private share conversions exist?

Answer: no. There is no t-private share conversion from Z_m to F_q when t ≥ 2 and q is coprime to m (generalized to Z_{m'} outputs). Consequently the Alon–Beimel–Lasri framework cannot yield t-private PIR at all — the entire matching-vector/decoding-polynomial machinery, the engine behind every subpolynomial IT-PIR communication result, is structurally confined to 1-private protocols.

Vault framing: this is the second structural negative in two weeks (after single-server code-based APIR, 2026/1224) and the mirror image of the positive Henzinger–Ragavan thread — the quasilinear-storage two-server IT-PIR line (ePrint 2025/2008) proceeds through DPFs, not matching vectors, so it is untouched. But for multi-server t-privacy (the setting that matters against colluding providers), the classic route is now formally walled off. Companion cataloguing: Beimel–Lasri, "PIR: Share Conversions vs. Decoding Polynomials" (ePrint 2026/1211, June 10) — the direct precursor paper — was also missing from this library and is now recorded.

Retrieve-Compute PIR — Realistic Non-Collusion (ePrint 2026/1372)

Paper: "Retrieve-Compute PIR and Its Applications" Authors: Benny Applebaum (TAU), Shahar Shechter (TAU) — the same pair as the CRYPTO 2026 arithmetic-PIR impossibility ePrint: https://eprint.iacr.org/2026/1372 (revised Aug 9 2026; slipped past the Aug 19 window check)

Two-server PIR achieves arbitrarily small polynomial communication but rests on "two servers that don't collude" — an assumption practitioners ridicule. RC-PIR re-architects it: one server is a normal compute server; the other is a retrieval-only server that stores a public encoding of the database and merely serves requested symbols/blocks, with zero PIR-specific computation. The authors argue such a server is instantiable with existing static-content or repository-hosting services (object storage, CDN, code forge) — grounding non-collusion in architectural reality (a file host has no incentive or mechanism to collude on PIR queries it cannot even recognize).

Construction from LPN over the ternary field with inverse-polynomial noise rate, with arbitrarily small polynomial communication and polynomial storage. Three applications, each new under LPN: - k-server PIR with privacy against any k−1 coalition; - k-server robust PIR for arbitrary monotone access structures (correctness when online set ∈ A, privacy against coalitions ∉ A); - k-party secure computation of lookup tables (extending to active security with honest majority, or via CRHFs).

Deployment reading: the retrieval-only server's encoding is public and static — this is exactly the shape of an IPFS pin, a GitHub Pages static host, or an S3 bucket fronting a PIR compute service. Of all the multi-server designs in this library, RC-PIR has the most credible deployment story for the "second server."

SK-PIR Exports: Encrypted Matrix-Vector Products (ePrint 2025/858, revised Aug 24)

Paper: "Encrypted Matrix-Vector Products from Secret Dual Codes" Authors: Fabrice Benhamouda, Caicai Chen, Shai Halevi, Yuval Ishai, Hugo Krawczyk, Tamer Mour, Tal Rabin, Alon Rosen ePrint: https://eprint.iacr.org/2025/858 (major revision Aug 24 2026)

The SK-PIR permuted-code blueprint (Boyle–Ishai–Pass–Wootters / Canetti–Holmgren–Richelson lineage, benchmarked in 2026/1480) generalizes: a client uploads an encryption of matrix M keeping a short key; online, encrypted query vectors q_i yield compact secret-shared M·q_i. Server learns nothing about M or q_i. Under LPN and the learning-subspace-with-noise (LSN) assumption, field-agnostic, and for ℓ in the hundreds the online cost is less than twice the plaintext matrix-vector product.

Applications: encrypted fuzzy search, secure ML inference. The significance for this library: the August SK-PIR milestone was not a one-off — the same secret dual-code technique is a general near-optimal secure-computation engine. Ishai appears on 2026/1224, 2026/1630, 2026/1480, 2025/858 — four ePrints in six weeks. The LPN renaissance (RC-PIR above is also LPN-based) is the quiet story of 2026: LPN is carrying SK-PIR, batch PIR, EMVP, and now RC-PIR simultaneously.

OKVS Fortnight (Aug 24–25)

  • Multi-PGBF (ePrint 2026/1774, Aug 24): Peelable Garbled Bloom Filters — onion-style peeling via counting Bloom filters, with recursive Multi-PGBF and clustered C-Multi-PGBF variants. Encoding 65.1–77.6% faster than RR (CCS'22); decoding 28.6–62.4% faster than RR and 89.7–96.3% faster than RB-OKVS (USENIX'23); drops into state-of-the-art two-party and multi-party PSI (EUROCRYPT'21, USENIX'24) with net speedups. OKVS is the substrate of keyword PIR and PSI alike — encoding speed directly widens the practical keyword-PIR envelope.
  • Updatable MPSI (ePrint 2026/1772, Aug 24): multi-party PSI via function secret sharing + OKVS with optimal one-pass online interaction, plus an updatable extension whose cost scales with the delta, not the dataset (49.1× vs GLW+24 at 140 parties, 2^20 items, WAN).

Together with UOKVS (2026/1590, recorded Aug 19), three updatable/efficient OKVS results in fourteen days. The 2025-era static OKVS picture (Garimella et al., CRYPTO 2021) is being replaced by a dynamic, access-controlled, multi-party generation.

Deployment — Kohaku Aug 21 Batch (GitHub-verified)

  • Releases (all published Aug 21 2026): @kohaku-eth/railgun@0.0.1-alpha.30, @kohaku-eth/tornado-cash@0.0.2-alpha.21, @kohaku-eth/privacy-pools@0.0.2-alpha.16, @kohaku-eth/plugins@0.0.1-alpha.13, and @kohaku-eth/provider@0.1.0-alpha.9 — a provider package not present in the Aug 8 batch, now versioned at 0.1.0-alpha (a higher major.minor than the plugins, suggesting it is nearer stabilization).
  • Commits since Aug 19: fix: utxo drain err on checksummed token address (#272), chore: version package (alpha) (#270). 399 stars (from 398).
  • Read the tea leaves carefully: provider is plausibly the wallet↫network abstraction layer through which a future PIR/ORAM read path would flow, but nothing PIR-specific has shipped. The Jan–Aug 2026 "Abstraction Core with Privacy by Design" window closes this week — the roadmap's private-reads milestone is now due, making the next release batch the highest-signal watch item in this section.

Repo quiet elsewhere: apple/swift-homomorphic-encryption at 655 stars (+18 since the June snapshot), last push Jul 23; google/hintless_pir pushed Jul 23; spiral-rs (18★) Mar 2026; ChalametPIR (16★) dormant since Jul 2025; frodo-pir unchanged since 2024 (deployment reference, as ever); Piano-PIR-new's 18 stars belie a 2023 pushed_at — the reference-skill note treating it as a live Go implementation should be read as "tutorial artifact," not active code.

Evidence at a Glance — New This Window

Paper / System Date Type Key Result Link
Alon, Limits of t-Private Share Conversion Aug 23 Negative No t-private Z_m→F_q share conversion for t≥2; matching-vector framework confined to 1-private PIR 2026/1780
Applebaum–Shechter, RC-PIR rev. Aug 9 Positive Retrieval-only second server (static host) under ternary LPN; k-server, robust, secure-LUT applications 2026/1372
Benhamouda et al., EMVP rev. Aug 24 Positive Encrypted M·q from secret dual codes, online <2× plaintext; LPN/LSN 2025/858
Multi-PGBF Aug 24 Systems OKVS encoding 65–78% faster than RR; decode ~90–96% faster than RB-OKVS 2026/1774
Updatable MPSI Aug 24 Positive One-pass online multi-party PSI; update-cost proportional to delta 2026/1772
Beimel–Lasri, Share Conversions vs Decoding Polynomials Jun 10 Survey/theory Precursor abstraction now catalogued 2026/1211
Kohaku release batch Aug 21 Deployment 4 plugin alpha bumps + new provider package; UTXO-drain fix github.com/ethereum/kohaku

Frontier Map Updates

  1. IT-PIR / matching vectors (WALLED): t-private route through share conversions closed (2026/1780). The Henzinger–Ragavan DPF-based line and fewer-server PIR (2026/1515) are unaffected.
  2. LPN consolidation: RC-PIR (ternary LPN) + EMVP (LPN/LSN) + SK-PIR (LPN/permuted codes) — LPN is now the workhorse assumption across three PIR families. 2026 is to LPN what 2023–24 were to LWE.
  3. Deployment realism: RC-PIR's retrieval-only static host is the first multi-server design whose non-collusion assumption maps onto commodity infrastructure.
  4. OKVS dynamics: three updatable/fast OKVS results in 14 days; keyword-PIR and PSI backends are being retooled.
  5. Ethereum: Kohaku's new provider package + the closing of the Jan–Aug roadmap window = private-reads watch enters its highest-priority week.

Watchlist — Next 7–14 Days