Please note: This master’s thesis presentation will take place online.
Ali Ghadirli, Master’s candidate
David R. Cheriton School of Computer Science
Supervisor: Professor Mohammad Hajiabadi
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 important questions. 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 Srinsivan 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.
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. In addition, it allows the parties to reuse the first messages in case the functionality of the protocol changes but the input of the party remains unchanged.
Our main result in this paper is to prove an impossibility result: We show that two-round MPC based on 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.