cPIR with total communication below n ⇒ Non-trivial cPIR

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

Statement

A PIR scheme with total communication below $n$ is non-trivial: for the same $n$, the server alone sends fewer than $n$ bits, and perfect correctness meets the error bound $1/(8n)$ — folklore.