One-round sublinear cPIR ⇒ cPIR with total communication below n

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

Statement

A one-round sublinear PIR scheme with $|q|+|a|\le p(\lambda )\cdot n^c$ for a polynomial $p$ and a constant $c<1$ has total communication below $n$ on databases of $n(\lambda )>p(\lambda {)}^{1/(1-c)}$ bits, a polynomial size — folklore.