ACM Asia Conference on Computer and Communications Security (ASIA CCS)
MYao: Efficient Multiparty “Yao” Garbled Circuits with Row Reduction and Half Gates
Aner Ben-Efraim, Lior Breitman, Jonathan Bronshtein, Olga V. Nissenbaum, Eran Omri
Abstract
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.