Non-trivial cPIR ⇒ OWF

Standard model · BIKM99

Statement

If a non-trivial single-server PIR scheme exists, perfectly correct and with the server sending fewer than $n$ bits on $n$-bit databases for some polynomial $n(\lambda )$, then one-way functions exist — 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 assume 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.