k Round Multiparty Computation from k Round Oblivious Transfer via Garbled Interactive Circuits
We present new constructions of round efficient, or even round optimal, Multi Party Computation (MPC) protocols from Oblivious Transfer (OT) protocols. Our constructions establish a tight connection between MPC and OT: In the setting of semi honest security, for any (k \ge 2\ k round semi honest OT is necessary and complete for k round semi honest MPC. In the round optimal case of (k 2\ we obtain 2 round semi honest MPC from 2 round semi honest OT, resolving the round complexity of semi honest MPC assuming weak and necessary assumption. In comparison, previous 2 round constructions rely on either the heavy machinery of indistinguishability obfuscation or witness encryption, or the algebraic structure of bilinear pairing groups. More generally, for an arbitrary number of rounds k, all previous constructions of k round semi honest MPC require at least OT with (k' rounds for (k' \le \lfloor k/2 \rfloor
EUROCRYPT