Aarhus University Seal

Secure Multiparty Computation with Free Branching

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review

  • Aarushi Goel, Johns Hopkins University
  • ,
  • Mathias Hall-Andersen
  • 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 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.

Original languageEnglish
Title of host publicationAdvances in Cryptology – EUROCRYPT 2022 : 41st Annual International Conference on the Theory and Applications of Cryptographic Techniques, 2022, Proceedings
EditorsOrr Dunkelman, Stefan Dziembowski
Number of pages30
PublisherSpringer
Publication yearMay 2022
Pages397-426
ISBN (print)9783031069437
ISBN (Electronic)978-3-031-06944-4
DOIs
Publication statusPublished - May 2022
Event41st Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2022 - Trondheim, Norway
Duration: 30 May 20223 Jun 2022

Conference

Conference41st Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2022
LandNorway
ByTrondheim
Periode30/05/202203/06/2022
SeriesLecture Notes in Computer Science (LNCS)
Volume13275
ISSN0302-9743

Bibliographical note

Publisher Copyright:
© 2022, International Association for Cryptologic Research.

See relations at Aarhus University Citationformats

ID: 276767859