Malicious OT ⇒ COM (Kilian)

Fully-black-box reduction · standard model · Kil88, Can00 · 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

Kilian’s commitment, which is statistically hiding and statistically binding in the OT-hybrid model (ideal OT ⇒ COM) — Kil88, is a computationally hiding and computationally binding bit commitment when each call to the ideal OT functionality is run as a sequential execution of an OT protocol with malicious security, since sequential composition lets each ideal call be replaced by a real execution in turn — Can00.

Sketch

Replace the $n\lambda$ ideal calls by real executions one at a time. A corrupted receiver in the hiding game, or a corrupted committer in the binding game, is a malicious party of each OT execution, so each replacement changes the probability that the adversary wins by at most the OT protocol’s simulation advantage, and the hybrid-model bounds hold against the resulting efficient adversary — standard.

Notes

• Binding uses that a deviating committer cannot learn which bits arrived, and hiding that a deviating receiver cannot learn the bits it missed, so the argument needs malicious security; the semi-honest sender- and receiver-privacy games say nothing about deviating parties — standard. Semi-honest OT gives maliciously secure OT (OT ⇒ malicious OT) — Hai08.
• The commitment is the first step of Kilian’s proof that OT is complete for secure computation (ideal OT ⇒ 2PC) — Kil88.