TDP ⇒ cPIR with total communication below n (Kushilevitz–Ostrovsky)

Standard model · KO00

Statement

If trapdoor permutations exist, there is a perfectly correct single-server PIR scheme for $n$-bit databases in which the client sends $O({\lambda }^2)$ bits and the server $n-cn/\lambda$ bits, for any constant $c$, so total communication is below $n$ once $n$ is large relative to $\lambda$, for example $\lambda =n^{\epsilon }$ for small $\epsilon$ — KO00. The protocol is interactive and uses interactive hashing.

Notes

• The saving cannot be improved much by black-box means: in every fully-black-box, polynomially security-preserving construction of single-server PIR from trapdoor permutations, the server sends $\Omega (n)$ bits — HHS08.
• The scheme yields 1-out-of-$n$ OT with communication below $n$ from trapdoor permutations — KO00.
• Polylogarithmic communication is known only from specific assumptions, such as Φ-hiding — CMS99.