cPIR with total communication below n ⇒ OT

Standard model · DMO00

Statement

Any single-server PIR with total communication $c(n)<n$ on an $n$-bit database, non-trivial in DMO00’s sense, implies OT — DMO00. Such 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 PIR with total communication below $n$ (DMO00’s non-trivial PIR), the latter by composition with IR89, which rules out relativizing constructions of key agreement from one-way permutations — DMO00.