Ideal OT ⇒ COM (Kilian)

Free reduction · standard model · Kil88 · security loss: statistical: hiding error at most $\lambda \cdot 2^{-n}$ and binding error $2^{-\lambda }$

Statement

In the OT-hybrid model, where the committer and the receiver may call an ideal OT functionality, there is a bit commitment that is statistically hiding and statistically binding, with no complexity assumption — 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

• Running each ideal call as an execution of an OT protocol with malicious security gives a computationally hiding and binding commitment (malicious OT ⇒ COM) — Kil88.
• The commitment is the first step of Kilian’s proof that OT is complete for secure computation (ideal OT ⇒ 2PC) — Kil88.