Random OT ⇒ OT

Fully-black-box reduction · standard model · Bea95 · security loss: none (perfect security)

Statement

A random OT correlation — the sender holds uniform $(r_0,r_1)$, the receiver a uniform bit $c^{\prime }$ and $r_{c^{\prime }}$ — yields perfectly secure chosen-input OT with two messages: the receiver sends $e=c\oplus c^{\prime }$, the sender replies $(y_0,y_1)=(x_0\oplus r_e,x_1\oplus r_{1\oplus e})$, and the receiver outputs $y_c\oplus r_{c^{\prime }}$ — Bea95.

Sketch

The receiver’s message $e=c\oplus c^{\prime }$ is uniform independently of $c$, since $c^{\prime }$ is uniform. Each $x_j$ is one-time-padded with $r_{j\oplus e}$, which the receiver holds exactly when $j=c$ (since $c\oplus e=c^{\prime }$), and $r_{1\oplus c^{\prime }}$ is uniform given the receiver’s view.

Notes

• Efficiency: the online phase sends one bit from the receiver and two strings from the sender and computes only XORs, so the public-key cost of OT moves entirely to an input-independent offline phase — Bea95.