No polynomially-preserving fully-black-box reduction from TDP to PIR with polylogarithmic communication
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
- For perfectly correct one-round schemes with communication , , the same theorem gives 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.