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

Unconditional · against fully-black-box reductions · HHS08

Statement

In every polynomially-preserving fully-black-box construction of single-server PIR on -bit databases from a family of trapdoor permutations, with as the security parameter, so that the security reduction inverts permutations on -bit inputs by running the adversary only on databases of bits, the server sends bits — HHS08. The bound allows a randomized server and a client that fails 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 that is polynomially preserving in this sense when run with yields one.

Notes