No polynomially-preserving fully-black-box reduction from enhanced TDP to PIR with polylogarithmic communication

Unconditional · against fully-black-box reductions · HHS08

Statement

The bound on the bits the server sends, in every polynomially-preserving fully-black-box construction of single-server PIR on -bit databases from trapdoor permutations, with as the security parameter, holds for the most generic form of trapdoor permutations, including enhanced ones, and for clients that fail to output with probability negligible in — HHS08. A scheme with polylogarithmic communication, run on -bit databases with for a large constant , has correctness error and adversary advantage negligible in and server communication , so no construction from an enhanced trapdoor permutation that is polynomially preserving in this sense when run with yields one.

Notes