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

Unconditional · against fully-black-box reductions · HHS08

Statement

The $\Omega (n)$ bound on the bits the server sends, in every polynomially-preserving fully-black-box construction of single-server PIR from trapdoor permutations, holds for the most generic form of trapdoor permutations, including enhanced ones — HHS08. A one-round sublinear scheme has server communication $o(n)$ on databases of large polynomial size, so no such construction yields one from an enhanced trapdoor permutation.

Notes

• The same theorem for standard trapdoor permutations is No polynomially-preserving fully-black-box reduction from TDP to one-round sublinear cPIR — HHS08.
• Fully-black-box constructions are a more restricted class than black-box constructions in general, so the theorem does not exclude constructions outside it — HHS08.