MYao: Efficient Multiparty "yao" Garbled Circuits with Row Reduction and Half Gates

Garbled circuits are a powerful and important cryptographic primitive, introduced by Yao [FOCS 1986] for secure two-party computation. Beaver, Micali and Rogaway (BMR) [STOCS 1990] extended the garbled circuit technique to construct the first constant-round secure multiparty computation (MPC) protocol. In the BMR protocol, the garbled circuit size grows linearly and the online computation time grows quadratically with the number of parties. Previous solutions to avoid this relied on key-homomorphic PRFs, incurring a large garbled circuit size and slow online computation time.We present MYao, a new multiparty protocol for achieving a "Yao"garbled circuit, i.e., the garbled circuit size and online computation time are independent of the number of parties. The key innovation is that the parties collaboratively compute the PRF in MPC, which was previously believed to be inefficient. In this paper, we challenge this long-standing assumption by basing the garbled circuit construction on "MPC-friendly"PRFs. One of the highlights of our new technique is that we are able to achieve, for the first time, full row-reduction in multiparty garbled circuits. To achieve this optimization without increasing the number of rounds, we utilize free-XOR and half gates, presenting a new technique for choosing the keys, based on a naturally occurring relation between the 2 keys of the 2 half-gates.MYao reduces the garbled circuit size by more than 90%, the total communication by more than 75%, and the online phase time by more than 10%, compared to all known solutions based on key-komomorphic PRFs, thus substantially improving the overall efficiency in both the offline and the online phases. Furthermore, although MYao requires more communication than BMR, especially in the offline phase, MYao significantly improves over semi-honest BMR in online efficiency when the number of parties exceeds 80. Additionally, MYao's garbled circuit is smaller than a BMR garbled circuit for any number of parties, and by more than an order of magnitude when the number of parties exceeds 15.