PIR with polylogarithmic communication ⇒ Non-trivial cPIR

Fully-black-box reduction · standard model · folklore · security loss: none

Statement

A PIR scheme with polylogarithmic communication is non-trivial: if its communication is at most $p(\lambda ,\log n)$ and its correctness error is a negligible $\epsilon (\lambda )$, then for $n(\lambda )={\lambda }^c$ with $c$ large enough that $p(\lambda ,c\log \lambda )<{\lambda }^c$ for all large $\lambda$, the server sends fewer than $n$ bits and $\epsilon (\lambda )\le 1/(8n(\lambda ))$ for all large $\lambda$ — folklore.

Notes

• With BIKM99’s theorem, such schemes imply one-way functions; that theorem allows retrieval error up to $1/(8n)$, which a negligible error meets — BIKM99.