Paper 2019/214

Four-Round Secure Multiparty Computation from General Assumptions

Michele Ciampi and Rafail Ostrovsky

Abstract

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.