We present a round-efficient black-box construction of a general multi-party computation (MPC) protocol that satisfies composability in the plain model. The security of our protocol is proven in the angel-based UC framework [Prabhakaran and Sahai, STOC’04] under the minimal assumption of the existence of semi-honest oblivious transfer protocols. The round complexity of our protocol is $\max (\widetilde{O}(\log ^2n), O(R_{{{{\mathsf {O}}}{{\mathsf {T}}}}}))$ when the round complexity of the underlying oblivious transfer protocol is $R_{{{{\mathsf {O}}}{{\mathsf {T}}}}}$ . Since constant-round semi-honest oblivious transfer protocols can be constructed under standard assumptions (such as the existence of enhanced trapdoor permutations), our result gives a $\widetilde{O}(\log ^2n)$ -round protocol under these assumptions. Previously, only an $O(\max (n^{\epsilon }, R_{{{{\mathsf {O}}}{{\mathsf {T}}}}}))$ -round protocol was shown, where $\epsilon >0$ is an arbitrary constant. We obtain our MPC protocol by constructing a $\widetilde{O}(\log ^2n)$ -round CCA-secure commitment scheme in a black-box way under the assumption of the existence of one-way functions.We present a round-efficient black-box construction of a general multi-party computation (MPC) protocol that satisfies composability in the plain model. The security of our protocol is proven in the angel-based UC framework [Prabhakaran and Sahai, STOC’04] under the minimal assumption of the existence of semi-honest oblivious transfer protocols. The round complexity of our protocol is $$\max (\widetilde{O}(\log ^2n), O(R_{{{{\mathsf {O}}}{{\mathsf {T}}}}}))$$ when the round complexity of the underlying oblivious transfer protocol is $$R_{{{{\mathsf {O}}}{{\mathsf {T}}}}}$$ . Since constant-round semi-honest oblivious transfer protocols can be constructed under standard assumptions (such as the existence of enhanced trapdoor permutations), our result gives a $$\widetilde{O}(\log ^2n)$$ -round protocol under these assumptions. Previously, only an $$O(\max (n^{\epsilon }, R_{{{{\mathsf {O}}}{{\mathsf {T}}}}}))$$ -round protocol was shown, where $$\epsilon >0$$ is an arbitrary constant. We obtain our MPC protocol by constructing a $$\widetilde{O}(\log ^2n)$$ -round CCA-secure commitment scheme in a black-box way under the assumption of the existence of one-way functions.

Jan 1, 20140 citations

\max (\widetilde{O}(\log ^2n), O(R_{{{{\mathsf {O}}}{{\mathsf {T}}}}}))

when the round complexity of the underlying oblivious transfer protocol is

R_{{{{\mathsf {O}}}{{\mathsf {T}}}}}

. Since constant-round semi-honest oblivious transfer protocols can be constructed under standard assumptions (such as the existence of enhanced trapdoor permutations), our result gives a

\widetilde{O}(\log ^2n)

-round protocol under these assumptions. Previously, only an

O(\max (n^{\epsilon }, R_{{{{\mathsf {O}}}{{\mathsf {T}}}}}))

-round protocol was shown, where

\epsilon >0

is an arbitrary constant. We obtain our MPC protocol by constructing a

\widetilde{O}(\log ^2n)

-round CCA-secure commitment scheme in a black-box way under the assumption of the existence of one-way functions.