Cryptology ePrint Archive: Report 2014/557

Round-Efficient Black-Box Construction of Composable Multi-Party Computation

Susumu Kiyoshima

Abstract: We present a round-efficient black-box construction of a general MPC protocol that satisfies composability in the plain model. The security of our protocol is proven in angel-based UC framework under the minimal assumption of the existence of semi-honest oblivious transfer protocols. When the round complexity of the underlying oblivious transfer protocol is Round(OT), the round complexity of our protocol is max(\tilde{O}(log^2 n), O(Round(OT))). 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 \tilde{O}(log^2 n)-round protocol under these assumptions. Previously, only an O(max(n^{\epsilon}, Round(OT))-round protocol was shown, where \epsilon>0 is an arbitrary constant.

We obtain our MPC protocol by constructing a \tilde{O}(log^2 n)-round CCA-secure commitment scheme in a black-box way under the assumption of the existence of one-way functions.

Category / Keywords: foundations / composable security, CCA-secure commitment scheme

Original Publication (with major differences): IACR-CRYPTO-2014

Date: received 16 Jul 2014, last revised 16 Jul 2014

Contact author: kiyoshima susumu at lab ntt co jp

Available format(s): PDF | BibTeX Citation

Version: 20140718:185102 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]