Abstract. Protocols for secure multiparty computation (MPC) can be divided into two types: (1) protocols that only guarantee security in the presence of an honest majority, and (2) protocols that guarantee security even when there is no honest majority. Known protocols of the first type are typically much more efficient than known protocols of the second type. This is true even in hybrid models that allow oracle access to ideal cryptographic primitives such as oblivious transfer (OT). Motivated by this efficiency gap, we present an efficient compiler for transforming MPC protocols of the first type into MPC protocols of the second type in the OT-hybrid model. More generally, our compiler combines a protocol of the first type with a protocol of the second type, but where the security of the latter only needs to hold against semi-honest adversaries. This compiler follows the "MPC in the head" approach initiated by Ishai, Kushilevitz, Ostrovsky, and Sahai (STOC '07) and further developed by Harnik, Ishai, Kushilevitz, and Nielsen (TCC '08). Combining our compiler with variants of protocols from the literature, we get several applications for secure two-party computation and for MPC with no honest majority. These include: -Constant-rate two-party computation in the OT-hybrid model. Applying our compiler to a variant of an efficient MPC protocol of Damgård and Ishai (Crypto '06), We obtain a statistically (UC) secure two-party protocol in the OT-hybrid model that can evaluate a general circuit C of size s with a total communication complexity of O(s). (For simplicity, we ignore from here on additive terms that depend polynomially on the security parameter k, the circuit depth, and log s. These terms become dominated by the leading term in most typical cases of large circuits.) This improves over the O(k 3 s) complexity of the best previous protocol, and matches the best asymptotic complexity in the semi-honest model. The above result generalizes to a constant number of parties. Supported in part by ISF grant 1310/06, BSF grant 2004361, and NSF grants 0205594, 0430254, 0456717, 0627781, 0716389. Partially supported by NSF grants CNS 07-16626 and CNS 07-47027. This research was supported in part from NSF grants 0627781, 0716389, 0456717, and 0205594, a subgrant from SRI as part of the Army Cyber-TA program, an equipment grant from Intel, an Alfred P. Sloan Foundation Fellowship, and an Okawa Foundation Research Grant. -Extending OTs in the malicious model. We obtain a protocol for generating many OTs from few OTs whose amortized cost in communication and cryptographic computation is a constant multiple of the efficient protocol for the semi-honest model given by Ishai, Kilian, Nissim, and Petrank (Crypto '03). This protocol can be used for efficiently implementing an off-line precomputation of OTs required by our protocols in the OT-hybrid model. -Black-box constructions for constant-round MPC with no honest majority. We apply our general compiler to a variant of an MPC protocol of Damgård and Ishai (Crypto '05) to obtain general computationally secure MPC protocols in the OT-hybrid model that use only a constant number of rounds, and only make a black-box access to a pseudorandom generator. This provides a very different alternative to a similar result for the two party case that was recently obtained by Lindell and Pinkas (Eurocrypt '07), and gives the first constant-round protocols for three or more parties that only make a black-box use of cryptographic primitives (and avoid expensive zero-knowledge proofs).
Recently, Ishai et al. constructed UC secure protocol with malicious majority in the OT hybrid model running in (large) constant rounds REF (see Fig 1) .
Founding Cryptography on Oblivious Transfer --- Efficiently
CRYPTO
Computer Science