International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: Secure Multiparty Computation with Free Branching

Aarushi Goel , Johns Hopkins University
Mathias Hall-Andersen , Aarhus University
Aditya Hegde , Johns Hopkins University
Abhishek Jain , Johns Hopkins University
Search ePrint
Search Google
Presentation: Slides
Conference: EUROCRYPT 2022
Abstract: We study secure multi-party computation (MPC) protocols for branching circuits that contain multiple sub-circuits (i.e., branches) and the output of the circuit is that of single ``active'' branch. Crucially, the identity of the active branch must remain hidden from the protocol participants. While such circuits can be securely computed by evaluating each branch and then multiplexing the output, such an approach incurs a communication cost linear in the size of the entire circuit. To alleviate this, a series of recent works have investigated the problem of reducing the communication cost of branching executions inside MPC (without relying on fully homomorphic encryption). Most notably, the stacked garbling paradigm [Heath and Kolesnikov, CRYPTO'20] yields garbled circuits for branching circuits whose size only depends on the size of the largest branch. Presently, however, it is not known how to obtain similar communication improvements for secure computation involving {\em more than two parties}. In this work, we provide a generic framework for branching multi-party computation that supports {\em any number of parties}. The communication complexity of our scheme is proportional to the size of the largest branch and the computation is linear in the size of the entire circuit. We provide an implementation and benchmarks to demonstrate practicality of our approach.
Video from EUROCRYPT 2022
  title={Secure Multiparty Computation with Free Branching},
  author={Aarushi Goel and Mathias Hall-Andersen and Aditya Hegde and Abhishek Jain},