Paper 2023/901

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

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 a 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 more than two parties. In this work, we provide a generic framework for branching multi-party computation that supports 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.

Available format(s)
Cryptographic protocols
Publication info
A minor revision of an IACR publication in EUROCRYPT 2022
Secure Computationbranching circuit
Contact author(s)
aarushi goel794 @ gmail com
ma @ cs au dk
ahegde @ cs jhu edu
abhishek @ cs jhu edu
2023-06-12: approved
2023-06-09: received
See all versions
Short URL
Creative Commons Attribution


      author = {Aarushi Goel and Mathias Hall-Andersen and Aditya Hegde and Abhishek Jain},
      title = {Secure Multiparty Computation with Free Branching},
      howpublished = {Cryptology ePrint Archive, Paper 2023/901},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.