OT ⇒ COM

Fully-black-box reduction · standard model · Kil88 · security loss: statistical in the OT-hybrid model: hiding error at most $\lambda \cdot 2^{-n}$ and binding error $2^{-\lambda }$; a real OT protocol adds its simulation advantage once per transfer, $n\lambda$ transfers in all

Statement

OT implies COM with no further assumption: in the OT-hybrid model there is a bit commitment that is statistically hiding and statistically binding — Kil88.

Sketch

To commit to $b$, the committer sends uniform bits $r_1,\dots ,r_n$ by Rabin OT, equivalent to OT (Rabin OT ⇔ OT), and then $c=b\oplus r_1\oplus \cdots \oplus r_n$; to open, it reveals $b$ and every $r_i$, which the receiver checks against the bits it received. Hiding holds because the receiver misses some $r_i$, leaving the parity uniform, except with probability $2^{-n}$; binding holds because opening to $1-b$ flips an odd number of the $r_i$, and each flipped bit is caught with probability $1/2$ since the committer does not learn which bits arrived. Committing in $\lambda$ independent copies gives hiding error at most $\lambda \cdot 2^{-n}$ and binding error $2^{-\lambda }$ — standard.

Notes

• The commitment is the first step of Kilian’s proof that OT is complete for secure computation (OT ⇒ MPC) — Kil88.