Paper 2019/214

Four-Round Secure Multiparty Computation from General Assumptions

Michele Ciampi and Rafail Ostrovsky


In this work we continue the study on the round complexity of secure multi-party computation with black-box simulation in the simultaneous broadcast model where all the parties get the output. In Eurocrypt 2016 Garg at al. show that four rounds are necessary to obtain a secure multi-party computation protocol for any function in the plain model. Many different works have tried to show that, relying on standard assumptions, four rounds are also sufficient for MPC. In Crypto 2017 Ananth et al. and in TCC 2017 Brakerski at al. propose a four-round protocol based on quasi-polynomial time number theoretic assumptions. In Crypto 2018 the two independent works of Badrinarayanan et al. and Halevi at al. show how reach the four-round barrier relying on number theoretic polynomial-time assumptions. In this work we propose a compiler that takes as input a three-round sub-exponentially secure oblivious transfer protocol, and outputs a four-round MPC protocol. Our compiler is also based on sub-exponentially secure two-round witness indistinguishable proof (zap). We also show how to obtain three-round OT assuming sub-exponentially secure trapdoor permutations and zap. As a corollary we obtain the first four-round MPC protocol that relies on general assumptions.

Available format(s)
Cryptographic protocols
Publication info
Preprint. MINOR revision.
multi-party computationoblivious transferround optimal
Contact author(s)
mciampi @ ed ac uk
rafail @ cs ucla edu
2019-03-19: revised
2019-02-27: received
See all versions
Short URL
Creative Commons Attribution


      author = {Michele Ciampi and Rafail Ostrovsky},
      title = {Four-Round Secure Multiparty Computation from General Assumptions},
      howpublished = {Cryptology ePrint Archive, Paper 2019/214},
      year = {2019},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.