Non-trivial cPIR ⇒ OT

Standard model · DMO00

Statement

Any non-trivial single-server PIR, with total communication $c(n)<n$ on an $n$-bit database, implies OT with communication $c(n)\cdot \mathrm{poly}(\lambda )$ — DMO00. Non-trivial single-server PIR is therefore complete for secure two-party and multi-party computation — DMO00.

Notes

• The result is strong evidence that one-way functions are necessary but not sufficient for non-trivial PIR, the latter by composition with IR89, which rules out relativizing constructions of key agreement from one-way permutations — DMO00.