No polynomially-preserving black-box reduction from TDP to one-round sublinear cPIR

Unconditional · HHS08

Statement

In every polynomially-preserving construction of single-server PIR that uses a family of trapdoor permutations, enhanced ones included, only as a black box, the server sends $\Omega (n)$ bits on $n$-bit databases, so downloading the database is optimal up to a constant factor — HHS08. A one-round sublinear scheme has server communication at most $p(\lambda )\cdot n^c=o(n)$ on databases of large polynomial size, so no such construction yields one.

Notes

• The proof combines a lower bound on the sender’s communication in the commit stage of black-box statistically hiding bit commitments from trapdoor permutations, matching the scheme of NOVY (OWP ⇒ Statistically hiding COM), with a reduction from statistically hiding commitments to low-communication single-server PIR that essentially preserves the PIR’s communication, improving that of BIKM99 — HHS08.
• The bound improves the $\Omega (n/\log n)$ lower bound of HHRS07 — HHS08.
• The trapdoor-permutation scheme of KO00, whose server sends $n-cn/\lambda$ bits, is therefore within a constant factor of optimal among such constructions — HHS08.