OWF ⇒ Secret-Key PIR (SK-PIR)

Standard model · BM26

Statement

If one-way functions exist, there is a secret-key PIR scheme for size-$N$ databases with online communication $\tilde{O}(\sqrt{N})$ per query and, more generally, for all $N_c,N_s$ with $N_c\cdot N_s=N$, one with client-to-server communication $\tilde{O}(N_c)$ and server-to-client communication $N_s$ — BM26.

Notes

• Under high-noise LPN, communication drops to $O(N^{\epsilon })$ for every constant $\epsilon >0$ — CIMR25 (High-noise LPN ⇒ Secret-Key PIR (SK-PIR)).
• Without the secret-key preprocessing, single-server PIR with total communication below $n$ implies OT — DMO00 (cPIR with total communication below n ⇒ OT).