Symmetric private information retrieval (Single-server) ⇒ OT

Fully-black-box reduction · standard model · folklore · security loss: none: an adversary against receiver or sender privacy is a query-privacy or data-privacy adversary against the SPIR scheme with the same advantage

Statement

Single-server symmetric PIR implies OT: an SPIR protocol on database $(x_1,\dots ,x_n)$ with query index $c$ is a $1$-out-of-$n$ OT, with client privacy as receiver privacy and data privacy as sender privacy, and $n=2$ gives $1$-out-of-$2$ OT — folklore.

Sketch

With $\mathsf{pp}\leftarrow \mathsf{Setup}(1^{\lambda },1^n)$, the sender runs the server on database $(x_1,\dots ,x_n)$ and the receiver runs the client on index $c$, so SPIR correctness is OT correctness. The sender’s view is the server’s view ${\mathsf{V}}_S$ of an honest execution on the database the adversary chose, so an adversary against the semi-honest receiver-privacy game is a query-privacy adversary, in the form for several rounds, with the same advantage; the two admissible sender inputs of the semi-honest sender-privacy game are databases that agree at index $c$, on which data privacy makes the honest client’s views indistinguishable — standard.

Notes

• The converse is not known: SPIR is $1$-out-of-$n$ OT with total communication at most $p(\lambda )\cdot n^c$ for a polynomial $p$ and a constant $c<1$, and no construction of sublinear-communication PIR from OT alone is known — folklore.
• NP05’s $1$-out-of-$N$ OT uses only $\log N$ executions of $1$-out-of-$2$ OT; as a corollary, any single-server PIR, combined with that OT, transforms efficiently into one that also has data privacy — NP05.
• Single-server PIR with total communication below $n$, without data privacy, implies OT (cPIR with total communication below n ⇒ OT) and converts communication-efficiently into $1$-out-of-$n$ OT, which DMO00 call SPIR — DMO00.