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 computable from $\mathsf{pp}$, the query and the database the adversary chose, so an adversary against the semi-honest receiver-privacy game is a query-privacy adversary 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 communication sublinear in $n$, and no construction of sublinear-communication PIR from OT alone is known — folklore.
• Any single-server PIR becomes SPIR with $\log n$ additional invocations of $1$-out-of-$2$ OT — NP99.
• Non-trivial single-server PIR, without data privacy, implies OT (Non-trivial cPIR ⇒ OT) and converts communication-efficiently into $1$-out-of-$n$ OT (SPIR) — DMO00.