International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

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

Authors:
Susumu Kiyoshima
Download:
DOI: 10.1007/s00145-018-9276-1
Search ePrint
Search Google
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 (\widetilde{O}(\log ^2n), O(R_{{{{\mathsf {O}}}{{\mathsf {T}}}}}))$$ max ( O ~ ( log 2 n ) , O ( R O T ) ) when the round complexity of the underlying oblivious transfer protocol is $$R_{{{{\mathsf {O}}}{{\mathsf {T}}}}}$$ R O 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)$$ O ~ ( log 2 n ) -round protocol under these assumptions. Previously, only an $$O(\max (n^{\epsilon }, R_{{{{\mathsf {O}}}{{\mathsf {T}}}}}))$$ O ( max ( n ϵ , R O T ) ) -round protocol was shown, where $$\epsilon >0$$ ϵ > 0 is an arbitrary constant. We obtain our MPC protocol by constructing a $$\widetilde{O}(\log ^2n)$$ O ~ ( log 2 n ) -round CCA-secure commitment scheme in a black-box way under the assumption of the existence of one-way functions.
BibTeX
@article{jofc-2019-30146,
  title={Round-Efficient Black-Box Construction of Composable Multi-Party Computation},
  journal={Journal of Cryptology},
  publisher={Springer},
  volume={32},
  pages={178-238},
  doi={10.1007/s00145-018-9276-1},
  author={Susumu Kiyoshima},
  year=2019
}