Research output: Contribution to book/anthology/report/proceeding › Article in proceedings › Research › peer-review
Final published version
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 language | English |
---|---|
Title of host publication | Advances in Cryptology – EUROCRYPT 2022 : 41st Annual International Conference on the Theory and Applications of Cryptographic Techniques, 2022, Proceedings |
Editors | Orr Dunkelman, Stefan Dziembowski |
Number of pages | 30 |
Publisher | Springer |
Publication year | May 2022 |
Pages | 397-426 |
ISBN (print) | 9783031069437 |
ISBN (Electronic) | 978-3-031-06944-4 |
DOIs | |
Publication status | Published - May 2022 |
Event | 41st Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2022 - Trondheim, Norway Duration: 30 May 2022 → 3 Jun 2022 |
Conference | 41st Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2022 |
---|---|
Land | Norway |
By | Trondheim |
Periode | 30/05/2022 → 03/06/2022 |
Series | Lecture Notes in Computer Science (LNCS) |
---|---|
Volume | 13275 |
ISSN | 0302-9743 |
Publisher Copyright:
© 2022, International Association for Cryptologic Research.
See relations at Aarhus University Citationformats
ID: 276767859