Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2105.00732 · Journal of Cryptology

Characterization of Secure Multiparty Computation Without Broadcast

Ran Cohen, Iftach Haitner, Eran Omri, Lior Rotem

Published Sep 22, 2017• 9 citations
arXivHTMLPDF
DOI
10.1007/s00145-017-9264-x

Related papers

Characterization of Secure Multiparty Computation Without Broadcast

Ran Cohen, Iftach Haitner, Eran Omri +1 more

Lecture notes in computer science•Dec 18, 2015•14 citations

The Broadcast Message Complexity of Secure Multiparty Computation

Sanjam Garg, Aarushi Goel, Abhishek Jain

Lecture notes in computer science•Jan 1, 2019•2 citations

Broadcast-Efficient Secure Multiparty Computation.

Juan A. Garay, Clint Givens, Rafail Ostrovsky

Secure multiparty computation (MPC) is perhaps the most popular paradigm in the area of cryptographic protocols. It allows several mutually untrustworthy parties to jointly compute a function of their private inputs, without revealing to each other information about those inputs. In the case of unconditional (information-theoretic) security, protocols are known which tolerate a dishonest minority of players, who may coordinate their attack and deviate arbitrarily from the protocol specification. It is typically assumed in these results that parties are connected pairwise by authenticated, private channels, and that in addition they have access to a “broadcast ” channel. Broadcast allows one party to send a consistent message to all other parties, guaranteeing consistency even if the broadcaster is corrupted. Because broadcast cannot be simulated on the point-to-point network when more than a third of the parties are corrupt, it is impossible to construct general MPC protocols in this setting without using a broadcast channel (or some equivalent addition to the model). A great deal of research has focused on increasing the efficiency of MPC, primarily in terms of round complexity and communication complexity. In this work we propose a refinement of the round complexity which we term broadcast complexity. We view the broadcast channel as an expensive resource

•Jan 1, 2012•2 citations

Secure Multiparty Computation with Minimal Interaction

Yuval Ishai, Eyal Kushilevitz, Anat Paskin-Cherniavsky

Lecture notes in computer science•Jan 1, 2010•58 citations

An Efficient Construction of Non-Interactive Secure Multiparty Computation

Satoshi Obana, Maki Yoshida

Lecture notes in computer science•Jan 1, 2016•4 citations

Upper Bounds on the Communication Complexity of Optimally Resilient Cryptographic Multiparty Computation.

Martin Hirt, Jesper Buus Nielsen

Abstract. We give improved upper bounds on the communication complexity of optimally-resilient secure multiparty computation in the cryptographic model. We consider evaluating an n-party randomized function and show that if f can be computed by a circuit of size c, thenO(cn 2 κ) is an upper bound for active security with optimal resilience t<n/2and security parameter κ. This improves on the communication complexity of previous protocols by a factor of at least n. This improvement comes from the fact that in the new protocol, only O(n) messages (of size O(κ) each) are broadcast during the whole protocol execution, in contrast to previous protocols which require at least O(n) broadcasts per gate. Furthermore, we improve the upper bound on the communication complexity of passive secure multiparty computation with resilience t<n from O(cn 2 κ)toO(cnκ). This improvement is mainly due to a simple observation. 1

•Jan 1, 2004•0 citations
Secure multiparty computation (MPC) is perhaps the most popular paradigm in the area of cryptographic protocols. It allows several mutually untrustworthy parties to jointly compute a function of their private inputs, without revealing to each other information about those inputs. In the case of unconditional (information-theoretic) security, protocols are known which tolerate a dishonest minority of players, who may coordinate their attack and deviate arbitrarily from the protocol specification. It is typically assumed in these results that parties are connected pairwise by authenticated, private channels, and that in addition they have access to a “broadcast ” channel. Broadcast allows one party to send a consistent message to all other parties, guaranteeing consistency even if the broadcaster is corrupted. Because broadcast cannot be simulated on the point-to-point network when more than a third of the parties are corrupt, it is impossible to construct general MPC protocols in this setting without using a broadcast channel (or some equivalent addition to the model). A great deal of research has focused on increasing the efficiency of MPC, primarily in terms of round complexity and communication complexity. In this work we propose a refinement of the round complexity which we term broadcast complexity. We view the broadcast channel as an expensive resource
Abstract. We give improved upper bounds on the communication complexity of optimally-resilient secure multiparty computation in the cryptographic model. We consider evaluating an n-party randomized function and show that if f can be computed by a circuit of size c, thenO(cn 2 κ) is an upper bound for active security with optimal resilience t<n/2and security parameter κ. This improves on the communication complexity of previous protocols by a factor of at least n. This improvement comes from the fact that in the new protocol, only O(n) messages (of size O(κ) each) are broadcast during the whole protocol execution, in contrast to previous protocols which require at least O(n) broadcasts per gate. Furthermore, we improve the upper bound on the communication complexity of passive secure multiparty computation with resilience t<n from O(cn 2 κ)toO(cnκ). This improvement is mainly due to a simple observation. 1