OWF ⇒ PIR with client preprocessing (Piano)

Standard model · ZPZS24

Statement

If one-way functions exist, there is a single-server PIR with client preprocessing for $n$-bit databases stored unencoded, with client storage ${\tilde{O}}_{\lambda }(\sqrt{n})$, amortized online server and client computation $\tilde{O}(\sqrt{n})$ per query and online communication $O(\sqrt{n})$ per query — ZPZS24. Counting the offline phase, the bandwidth and computation per query are $\tilde{O}(\sqrt{n})$ — GZS24.

Notes

• Efficiency: for a 100 GB database of 1.6 billion entries, Piano’s online computation is 12 ms per query on one core — ZPZS24.
• Plinko has query time $\tilde{O}(n/r)$ for every client storage $r$, matching the lower bound $r\cdot t=\Omega (n)$ up to logarithmic factors, and worst-case $\tilde{O}(1)$ updates, using an invertible PRF that one-way functions give (PRF ⇒ iPRF) — HPPY25.
• From one-way functions there is also a single-server scheme with online bandwidth $\tilde{O}(n^{1/4})$, offline bandwidth and computation $\tilde{O}(n^{1/2})$ per query and client storage $\tilde{O}(n^{1/2})$ — GZS24 — and, combining client-side with server-side preprocessing at $n^{1+\epsilon }$ server space, one with polylogarithmic online bandwidth and with offline bandwidth and client space ${\tilde{O}}_{\lambda }(n^{1/2+\epsilon })$ — GZSP25.
• Under LWE, bandwidth drops to ${\tilde{O}}_{\lambda }(1)$ per query in a single round trip, with ${\tilde{O}}_{\lambda }(\sqrt{n})$ amortized computation and client storage — ZLTS23.
• Piano’s trade-off between client space and bandwidth is nearly optimal for schemes that use a one-way function as a black box — ISW24.