Paper 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 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).

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Published by the IACR in JOC 2018
Keywords
composable securityCCA-secure commitment scheme
Contact author(s)
kiyoshima susumu @ lab ntt co jp
History
2018-08-21: revised
2014-07-18: received
See all versions
Short URL
https://ia.cr/2014/557
License
Creative Commons Attribution
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.