When Is a Semi-honest Secure Multiparty Computation Valuable?

Koji Nuida

Koji Nuida

Secure multiparty computation (MPC) is a cryptographic technology to perform some computation on multiple parties' input data while concealing the individual inputs from other parties. For the case of semi-honest adversaries, the security definition in Goldreich's famous book is widely used as a standard definition. In this paper, however, we point out that there is an MPC protocol where a semi-honest adversary receives only a ciphertext of one-time pad with unknown key but the protocol is not secure under the standard security definition, which may look inconsistent with the perfect secrecy of one-time pad that its ciphertext leaks no information at all. We propose a variant of the security definition that resolves this issue. We also show that a somewhat restrictive version of the Composition Theorem holds for our modified security definition.

Rosario Gennaro, Yuval Ishai, Eyal Kushilevitz Z +1 more

Aner Ben-Efraim, Yehuda Lindell, Eran Omri

In the setting of secure multiparty computation, a set of parties with private inputs wish to compute some function of their inputs without revealing anything but their output. Over the last decade, the efficiency of secure two-party computation has advanced in leaps and bounds, with speedups of some orders of magnitude, making it fast enough to be of use in practice. In contrast, progress on the case of multiparty computation (with more than two parties) has been much slower, with very little work being done. Currently, the only implemented efficient multiparty protocol has many rounds of communication (linear in the depth of the circuit being computed) and thus is not suited for Internet-like settings where latency is not very low. In this paper, we construct highly efficient constant-round protocols for the setting of multiparty computation for semi-honest adversaries. Our protocols work by constructing a multiparty garbled circuit, as proposed in BMR (Beaver et al., STOC 1990). Our first protocol uses oblivious transfer and constitutes the first concretely-efficient constant-round multiparty protocol for the case of no honest majority. Our second protocol uses BGW, and is significantly more efficient than the FairplayMP protocol (Ben-David et al., CCS 2008) that also uses BGW.

Ivan Damgård, Yuval Ishai, Mikkel Krøigaard

Ran Cohen, Iftach Haitner, Eran Omri +1 more