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

Constant-Round Black-Box Construction of Composable Multi-Party Computation Protocol.

Susumu Kiyoshima, Yoshifumi Manabe, Tatsuaki Okamoto

Abstract. We present the first general MPC protocol that satisfies the following: (1) the con-struction is black-box, (2) the protocol is universally composable in the plain model, and (3) the number of rounds is constant. The security of our protocol is proven in angel-based UC security under the assumption of the existence of one-way functions that are secure against sub-exponential-time adversaries and constant-round semi-honest oblivious transfer protocols that are secure against quasi-polynomial-time adversaries. We obtain the MPC protocol by constructing a constant-round CCA-secure commitment scheme in a black-box way under the assumption of the existence of one-way functions that are secure against sub-exponential-time adversaries. To justify the use of such a sub-exponential hardness assumption in obtaining our constant-round CCA-secure commitment scheme, we show that if black-box reductions are used, there does not exist any constant-round CCA-secure commitment scheme under any falsifiable polynomial-time hardness assumptions. 1Abstract. We present the first general MPC protocol that satisfies the following: (1) the con-struction is black-box, (2) the protocol is universally composable in the plain model, and (3) the number of rounds is constant. The security of our protocol is proven in angel-based UC security under the assumption of the existence of one-way functions that are secure against sub-exponential-time adversaries and constant-round semi-honest oblivious transfer protocols that are secure against quasi-polynomial-time adversaries. We obtain the MPC protocol by constructing a constant-round CCA-secure commitment scheme in a black-box way under the assumption of the existence of one-way functions that are secure against sub-exponential-time adversaries. To justify the use of such a sub-exponential hardness assumption in obtaining our constant-round CCA-secure commitment scheme, we show that if black-box reductions are used, there does not exist any constant-round CCA-secure commitment scheme under any falsifiable polynomial-time hardness assumptions. 1

Jan 1, 20130 citations

Black-Box Constructions of Composable Protocols without Set-Up

Huijia Lin, Rafael Pass

Lecture notes in computer scienceJan 1, 20120 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.