OT ⇒ KE

Fully-black-box reduction · standard model · folklore · security loss: the sum of the sender-privacy and receiver-privacy advantages, up to constant factors

Statement

A semi-honest secure 1-out-of-2 OT protocol yields a key-agreement protocol secure against eavesdroppers: Alice and Bob run the OT with Alice as sender on uniform bits $(x_0,x_1)$ and Bob as receiver on a uniform choice bit $c$; Bob then sends $c$, and both output $x_c$ — folklore.

Sketch

Bob learns $x_c$ by correctness. An eavesdropper sees the OT transcript $\tau$ and then $c$. Receiver privacy makes $\tau$ independent of $c$ given $(x_0,x_1)$, and sender privacy makes $\tau$ independent of $x_{1-c}$ given $(c,x_c)$, both computationally; the two together make $\tau$ computationally independent of $(x_0,x_1,c)$, so $x_c$ is pseudorandom given $(\tau ,c)$. Repetition gives a longer key.

Notes

• The converse fails for fully-black-box constructions: PKE gives two-message key agreement, and no fully-black-box construction of OT from PKE exists — GKM+00.
• Through this implication, the IR89 separation of key agreement from one-way permutations also separates OT from them: No relativizing reduction from OWF to OT — IR89.