Non-trivial cPIR ⇒ OWF

Standard model · BIKM99

Statement

If a non-trivial single-server PIR scheme exists, in which for some polynomial $n(\lambda )$ the server sends fewer than $n$ bits on $n$-bit databases and retrieval fails with probability at most $1/(8n)$, then one-way functions exist — BIKM99. The proof is simpler for perfectly correct schemes; for them, saving a single bit over downloading the database already requires one-way functions — BIKM99.

Notes

• Trivial PIR, in which the server sends the whole database, is perfectly private with no assumption, so the bound $n$ is where computational assumptions start — BIKM99.
• The known stronger consequences hold for perfectly correct schemes with a deterministic server and stronger communication bounds: total communication below $n$ gives OT — DMO00 — and one-round communication $p(\lambda )\cdot n^c$ for a polynomial $p$ and a constant $c<1$ gives collision-resistant hashing — IKO05.
• A randomized server is no more general for this theorem, which bounds only the server’s communication: the client can choose the server’s coins for every round and send them before the server’s first message, adding a first client message if the server speaks first, which leaves the server’s communication, the correctness and the query privacy unchanged — folklore. The client’s messages grow by those coins, so this does not lift the deterministic-server condition of PIR with total communication below $n$.
• Constant error is also tolerated at lower communication: a PIR with error $1/4$ and communication complexity below $n/10$ bits implies one-way functions — BIKM99.
• A single-server PIR with communication at most $n/2$ bits yields a weakly binding, statistically hiding bit commitment with the PIR’s number of rounds — BIKM99; a variant of the construction essentially preserves the PIR’s communication, which turns commit-stage lower bounds into the linear lower bound for polynomially-preserving fully-black-box PIR from trapdoor permutations — HHS08.