Rabin OT ⇔ OT

Equivalence · fully-black-box reduction · standard model · Cre87

Statement

Rabin OT and 1-out-of-2 OT on bits are equivalent: each is realized from the other by an information-theoretically secure protocol making polynomially many calls, and the nontrivial direction builds 1-out-of-2 OT from $3n$ Rabin OTs with error exponentially small in $n$ — Cre87.

Sketch

The sender sends $3n$ uniform bits $r_i$ by Rabin OT; the receiver, who gets about half of them, announces disjoint sets $I_0,I_1$ of size $n$ with $I_c$ fully received, the sender replies $x_j\oplus {⨁}_{i\in I_j}{r}_i$ for $j\in \{0,1\}$, and the receiver unmasks $x_c$. Except with probability exponentially small in $n$ the receiver gets fewer than $2n$ bits, so one of $I_0,I_1$ contains a lost bit and the corresponding $x_j$ stays perfectly masked, while the sender cannot tell which set was fully received. Conversely, the sender puts $x$ in a uniform slot $s$ of one 1-out-of-2 OT, the other slot uniform, and then reveals $s$: the receiver’s uniform choice hits $s$ with probability exactly $1/2$, and receiver privacy hides whether it did.