Impossibility of Two-Round MPC with the Black-Box Use of Additive Homomorphic Encryption

Abstract

Minimizing the number of rounds in the context of the Multiparty Computation (MPC) realm with respect to an arbitrary number of semi-honest adversaries is considered one of the branches that has gotten attention from researchers recently. Garg et al. proved that two-round semi-honest MPC is impossible from black-box use of two-round oblivious transfer (OT). Before this work, Garg and Srinivasan and Benhamouda and Lin showed a construction of a two-round MPC with a non-black-box use of the underlying two-round OT. Constructions of cryptographic protocols with the black-box use of cryptographic primitives have the advantage of being more efficient compared to non-black-box constructions, since in these constructions treat the underlying primitives as oracles which simplifies protocol design and analysis, leading to potentially more efficient constructions. Reducing the number of rounds has the advantage of making parties able to send their first messages and go offline until all the other parties send their message of the second round and compute the output. Our main result in this paper is to prove an impossibility result: We show that a two-round MPC based on black-box use of additive homomorphic encryption is impossible. This result is stronger than the previous result by Garg et al., mainly because OT can be constructed using additive homomorphic encryption.