Secure MPC: Laziness Leads to GOD

Nathan Manohar


Secure multi-party computation (MPC) is a problem of fundamental interest in cryptography. Traditional MPC protocols treat a "lazy" party (one that behaves honestly but aborts in the middle of the protocol execution) as a corrupt party that is colluding with the other corrupt parties. However, this outlook is unrealistic, as there are various cases where an honest party may abort and turn "lazy" during the execution of a protocol without colluding with other parties. To address this gap, we initiate the study of what we call secure lazy multi-party computation with a formal definition that achieves meaningful correctness and security guarantees. We then construct a three-round lazy MPC protocol from standard cryptographic assumptions. Our protocol is malicious secure in the presence of a CRS and semi-malicious secure in the plain model without a CRS.

Using the techniques from above, we also achieve independently interesting consequences in the traditional MPC model. We construct the first round-optimal (three rounds) MPC protocol in the plain model (without a CRS) that achieves guaranteed output delivery (GOD) and is malicious-secure in the presence of an honest majority of parties. Previously, Gordon et al. [CRYPTO' 15] constructed a three-round protocol in the presence of a CRS that achieves GOD in the honest majority setting and also showed that it is impossible to construct two-round protocols for the same even in the presence of a CRS. Thus, our result is optimal.

Furthermore, all our above protocols have communication complexity proportional only to the depth of the circuit being evaluated.

The key technical tool in our above protocols is a primitive called threshold multi-key fully homomorphic encryption, which we define and construct assuming just learning with errors (LWE). We believe this primitive may be of independent interest.

Joint work with Saikrishna Badrinarayanan, Aayush Jain, and Amit Sahai.

Time and Place

Wednesday, May 30, 4:15pm
Gates 463A