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

Susumu Kiyoshima

##### Abstract

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(\tilde{O}(\log^2 n), O(R_{OT})) when the round complexity of the underlying oblivious transfer protocol is R_{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 a \tilde{O}(\log^2 n)-round protocol under these assumptions. Previously, only an O(\max(n^{\epsilon}, R_{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.

Note: A preliminary version of this paper was presented at CRYPTO 2014 (the main result remains the same).

Available format(s)
Category
Foundations
Publication info
Keywords
composable securityCCA-secure commitment scheme
Contact author(s)
kiyoshima susumu @ lab ntt co jp
History
2018-08-21: revised
See all versions
Short URL
https://ia.cr/2014/557

CC BY

BibTeX

@misc{cryptoeprint:2014/557,
author = {Susumu Kiyoshima},
title = {Round-Efficient Black-Box Construction of Composable Multi-Party Computation},
howpublished = {Cryptology ePrint Archive, Paper 2014/557},
year = {2014},
note = {\url{https://eprint.iacr.org/2014/557}},
url = {https://eprint.iacr.org/2014/557}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.