MISC: Multi-Input Secure Two-Party Computation

Secure multi-party computation (MPC) allows a group of parties to compute a function on their private inputs securely. Classic MPC protocols for two parties use either Yao’s garbled circuit (GC) or the Goldreich-Micali-Wigderson (GMW) protocol. In this paper, we propose MISC, a multi-input secure computation protocol, by combining GC and GMW in a novel way. MISC can evaluate multi-input AND gates, which can reduce the round complexity. Moreover, MISC reduces the communication overhead by 1.7x and 2.4x for 2-input and by 2x and 2.8x for 4-input AND gates compared to the state-of-the-art GMW-style and GC-style protocols, respectively. In order to use the MISC efficiently in different applications, we redesign common building block with multi-input AND gates such as Equality checking, Maxpool, Comparison, and Argmax/Argmin. Results on privacy-preserving applications, e.g., circuit-based private set intersection (PSI) and private machine learning (CNN inference) show that compared to GMW, MISC improves the total communication overhead by 3x and the total run time by 1.5x.