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

ACM SIGSAC Conference on Computer and Communications Security (CCS)

Optimizing Semi-Honest Secure Multiparty Computation for the Internet

Aner Ben-Efraim, Yehuda Lindell, Eran Omri

Published Oct 24, 2016• 92 citations
Publisher

Abstract

In the setting of secure multiparty computation, a set of parties with private inputs wish to compute some function of their inputs without revealing anything but their output. Over the last decade, the efficiency of secure two-party computation has advanced in leaps and bounds, with speedups of some orders of magnitude, making it fast enough to be of use in practice. In contrast, progress on the case of multiparty computation (with more than two parties) has been much slower, with very little work being done. Currently, the only implemented efficient multiparty protocol has many rounds of communication (linear in the depth of the circuit being computed) and thus is not suited for Internet-like settings where latency is not very low. In this paper, we construct highly efficient constant-round protocols for the setting of multiparty computation for semi-honest adversaries. Our protocols work by constructing a multiparty garbled circuit, as proposed in BMR (Beaver et al., STOC 1990). Our first protocol uses oblivious transfer and constitutes the first concretely-efficient constant-round multiparty protocol for the case of no honest majority. Our second protocol uses BGW, and is significantly more efficient than the FairplayMP protocol (Ben-David et al., CCS 2008) that also uses BGW.

DOI
10.1145/2976749.2978347

Related papers

A Framework for Constructing Fast MPC over Arithmetic Circuits with Malicious Adversaries and an Honest-Majority

Yehuda Lindell, Ariel Nof

Protocols for secure multiparty computation enable a set of parties to compute a function of their inputs without revealing anything but the output. The security properties of the protocol must be preserved in the presence of adversarial behavior. The two classic adversary models considered are semi-honest (where the adversary follows the protocol specification but tries to learn more than allowed by examining the protocol transcript) and malicious (where the adversary may follow any arbitrary attack strategy). Protocols for semi-honest adversaries are often far more efficient, but in many cases the security guarantees are not strong enough.

ACM SIGSAC Conference on Computer and Communications Security (CCS)•Oct 27, 2017•96 citations

On Multiparty Garbling of Arithmetic Circuits.

Aner Ben-Efraim

We initiate a study of garbled circuits that contain both Boolean and arithmetic gates in secure multiparty computation. In particular, we incorporate the garbling gadgets for arithmetic circuits recently presented by Ball, Malkin, and Rosulek (ACM CCS 2016) into the multiparty garbling paradigm initially introduced by Beaver, Micali, and Rogaway (STOC ’90). This is the first work that studies arithmetic garbled circuits in the multiparty setting. Using mixed Boolean-arithmetic circuits allows more efficient secure computation of functions that naturally combine Boolean and arithmetic computations. Our garbled circuits are secure in the semi-honest model, under the same hardness assumptions as Ball et al., and can be efficiently and securely computed in constant rounds assuming an honest majority.

•Jan 1, 2017•1 citation

Efficient Constant Round Multi-Party Computation Combining BMR and SPDZ.

Yehuda Lindell, Benny Pinkas B, Nigel Paul Smart +1 more

Abstract. Recently, there has been huge progress in the field of con-cretely efficient secure computation, even while providing security in the presence of malicious adversaries. This is especially the case in the two-party setting, where constant-round protocols exist that remain fast even over slow networks. However, in the multi-party setting, all concretely efficient fully-secure protocols, such as SPDZ, require many rounds of communication. In this paper, we present an MPC protocol that is fully-secure in the presence of malicious adversaries and for any number of corrupted par-ties. Our construction is based on the constant-round BMR protocol of Beaver et al., and is the first version of that protocol that is concretely efficient for the dishonest majority case. Our protocol includes an online phase that is extremely fast and mainly consists of each party locally evaluating a garbled circuit. For the offline phase we present both a generic construction (using any underlying MPC protocol), and a highly efficient instantiation based on the SPDZ proto-col. Our estimates show the protocol to be considerably more efficient than previous fully-secure multi-party protocols. 1

•Jan 1, 2015•0 citations

Towards Secure Multi-Party Computation on the Internet

Eduardo Soria-Vázquez

ulti-Party Computation (MPC) protocols allow a set of mutually distrustful parties to securely compute on their joint private inputs, maintaining the privacy of those.Since its early conception in the eighties, a plethora of research as well as some real world deployments have taken place, demonstrating the relevance of such an interesting mathematical problem.Nevertheless, most of the research and all deployments have focused on scenarios where both the number of parties and network latency are very low.This thesis lays out the first steps towards practical deployments of large-scale MPC, where many parties may be involved and they might only be connected through a high-latency network such as the Internet.Both theoretical and empirical evidence shows that non-constant-round protocols cannot perform well on slow networks for many functions.In order to overcome this issue, all the works in this thesis include concretely efficient constant-round protocols based on multi-party garbled circuits.Chapter 3 and Chapter 4 deal with the very strong setting where an active adversary corrupts all but one parties.The former achieves such goal by using homomorphic encryption for low-depth circuits.The latter, based on subsequent work, improves the theoretical understanding of the problem and utilises oblivious transfer to improve efficiency.In Chapter 5 we provide both constant and non-constant round protocols that can handle large numbers of parties more efficiently.We leverage our performance improvements by relaxing the setting where all but one parties are corrupted to one where a small minority of honest participants can be assumed.Concretely, such change allows to distribute secret key material so that each party only holds a 'short' part of the key.Security is then based on the concatenation of all honest parties' keys rather than on each party's individual key, improving both the communication and computation complexities.iii researcher.They would have not been the same without the support of family, friends and colleagues.I would like to start by thanking Nigel Smart for giving me this opportunity, being my advisor and introducing me to others in the community.Martijn Stam

•Feb 1, 2019•0 citations

Two-Thirds Honest-Majority MPC for Malicious Adversaries at Almost the Cost of Semi-Honest

Jun Furukawa, Yehuda Lindell

Secure multiparty computation (MPC) enables a set of parties to securely carry out a joint computation of their private inputs without revealing anything but the output. Protocols for semi-honest adversaries guarantee security as long as the corrupted parties run the specified protocol and ensure that nothing is leaked in the transcript. In contrast, protocols for malicious adversaries guarantee security in the presence of arbitrary adversaries who can run any attack strategy. Security for malicious adversaries is typically what is needed in practice (and is always preferred), but comes at a significant cost. In this paper, we present the first protocol for a two-thirds honest majority that achieves security in the presence of malicious adversariesat essentially the exact same cost as the best known protocols for semi-honest adversaries. Our construction is not a general transformation and thus it is possible that better semi-honest protocols will be constructed which do not support our transformation. Nevertheless, for the current state-of-the-art for many parties (based on Shamir sharing), our protocol invokes the best semi-honest multiplication protocol exactly once per multiplication gate (plus some additional local computation that is negligible to the overall cost). Concretely, the best version of our protocol requires each party to send on average of just 2 2/3 elements per multiplication gate (when the number of multiplication gates is at least the number of parties). This is four times faster than the previous-best protocol of Barak et al. (ACM CCS 2018) for small fields, and twice as fast as the previous-best protocol of Chida et al. (CRYPTO 2018) for large fields.

ACM SIGSAC Conference on Computer and Communications Security (CCS)•Nov 6, 2019•33 citations

Towards High-Throughput Secure MPC over the Internet: Communication-Efficient Two-Party Protocols and Its Application

Satsuya Ohata, Koji Nuida

Secure multi-party computation (MPC) allows a set of parties to compute a function jointly while keeping their inputs private. Compared with the MPC based on garbled circuits, some recent research results show that MPC based on secret sharing (SS) works at a very high speed. Moreover, SS-based MPC can be easily vectorized and achieve higher throughput. In SS-based MPC, however, we need many communication rounds for computing concrete protocols like equality check, less-than comparison, etc. This property is not suited for large-latency environments like the Internet (or WAN). In this paper, we construct semi-honest secure communication-efficient two-party protocols. The core technique is Beaver triple extension, which is a new tool for treating multi-fan-in gates, and we also show how to use it efficiently. We mainly focus on reducing the number of communication rounds, and our protocols also succeed in reducing the number of communication bits (in most cases). As an example, we propose a less-than comparison protocol (under practical parameters) with three communication rounds. This is less than a half compared with the previous work. Moreover, the number of communication bits is also $38.4\%$ fewer. As a result, total online execution time is $56.1\%$ shorter than the previous work adopting the same settings. Although the computation costs of our protocols are more expensive than those of previous work, we confirm via experiments that such a disadvantage has small effects on the whole online performance in the typical WAN environments.

•Jul 8, 2019•1 citation
In the setting of secure multiparty computation, a set of parties with private inputs wish to compute some function of their inputs without revealing anything but their output. Over the last decade, the efficiency of secure two-party computation has advanced in leaps and bounds, with speedups of some orders of magnitude, making it fast enough to be of use in practice. In contrast, progress on the case of multiparty computation (with more than two parties) has been much slower, with very little work being done. Currently, the only implemented efficient multiparty protocol has many rounds of communication (linear in the depth of the circuit being computed) and thus is not suited for Internet-like settings where latency is not very low. In this paper, we construct highly efficient constant-round protocols for the setting of multiparty computation for semi-honest adversaries. Our protocols work by constructing a multiparty garbled circuit, as proposed in BMR (Beaver et al., STOC 1990). Our first protocol uses oblivious transfer and constitutes the first concretely-efficient constant-round multiparty protocol for the case of no honest majority. Our second protocol uses BGW, and is significantly more efficient than the FairplayMP protocol (Ben-David et al., CCS 2008) that also uses BGW.
Protocols for secure multiparty computation enable a set of parties to compute a function of their inputs without revealing anything but the output. The security properties of the protocol must be preserved in the presence of adversarial behavior. The two classic adversary models considered are semi-honest (where the adversary follows the protocol specification but tries to learn more than allowed by examining the protocol transcript) and malicious (where the adversary may follow any arbitrary attack strategy). Protocols for semi-honest adversaries are often far more efficient, but in many cases the security guarantees are not strong enough.
We initiate a study of garbled circuits that contain both Boolean and arithmetic gates in secure multiparty computation. In particular, we incorporate the garbling gadgets for arithmetic circuits recently presented by Ball, Malkin, and Rosulek (ACM CCS 2016) into the multiparty garbling paradigm initially introduced by Beaver, Micali, and Rogaway (STOC ’90). This is the first work that studies arithmetic garbled circuits in the multiparty setting. Using mixed Boolean-arithmetic circuits allows more efficient secure computation of functions that naturally combine Boolean and arithmetic computations. Our garbled circuits are secure in the semi-honest model, under the same hardness assumptions as Ball et al., and can be efficiently and securely computed in constant rounds assuming an honest majority.
Abstract. Recently, there has been huge progress in the field of con-cretely efficient secure computation, even while providing security in the presence of malicious adversaries. This is especially the case in the two-party setting, where constant-round protocols exist that remain fast even over slow networks. However, in the multi-party setting, all concretely efficient fully-secure protocols, such as SPDZ, require many rounds of communication. In this paper, we present an MPC protocol that is fully-secure in the presence of malicious adversaries and for any number of corrupted par-ties. Our construction is based on the constant-round BMR protocol of Beaver et al., and is the first version of that protocol that is concretely efficient for the dishonest majority case. Our protocol includes an online phase that is extremely fast and mainly consists of each party locally evaluating a garbled circuit. For the offline phase we present both a generic construction (using any underlying MPC protocol), and a highly efficient instantiation based on the SPDZ proto-col. Our estimates show the protocol to be considerably more efficient than previous fully-secure multi-party protocols. 1
ulti-Party Computation (MPC) protocols allow a set of mutually distrustful parties to securely compute on their joint private inputs, maintaining the privacy of those.Since its early conception in the eighties, a plethora of research as well as some real world deployments have taken place, demonstrating the relevance of such an interesting mathematical problem.Nevertheless, most of the research and all deployments have focused on scenarios where both the number of parties and network latency are very low.This thesis lays out the first steps towards practical deployments of large-scale MPC, where many parties may be involved and they might only be connected through a high-latency network such as the Internet.Both theoretical and empirical evidence shows that non-constant-round protocols cannot perform well on slow networks for many functions.In order to overcome this issue, all the works in this thesis include concretely efficient constant-round protocols based on multi-party garbled circuits.Chapter 3 and Chapter 4 deal with the very strong setting where an active adversary corrupts all but one parties.The former achieves such goal by using homomorphic encryption for low-depth circuits.The latter, based on subsequent work, improves the theoretical understanding of the problem and utilises oblivious transfer to improve efficiency.In Chapter 5 we provide both constant and non-constant round protocols that can handle large numbers of parties more efficiently.We leverage our performance improvements by relaxing the setting where all but one parties are corrupted to one where a small minority of honest participants can be assumed.Concretely, such change allows to distribute secret key material so that each party only holds a 'short' part of the key.Security is then based on the concatenation of all honest parties' keys rather than on each party's individual key, improving both the communication and computation complexities.iii researcher.They would have not been the same without the support of family, friends and colleagues.I would like to start by thanking Nigel Smart for giving me this opportunity, being my advisor and introducing me to others in the community.Martijn Stam
Secure multiparty computation (MPC) enables a set of parties to securely carry out a joint computation of their private inputs without revealing anything but the output. Protocols for semi-honest adversaries guarantee security as long as the corrupted parties run the specified protocol and ensure that nothing is leaked in the transcript. In contrast, protocols for malicious adversaries guarantee security in the presence of arbitrary adversaries who can run any attack strategy. Security for malicious adversaries is typically what is needed in practice (and is always preferred), but comes at a significant cost. In this paper, we present the first protocol for a two-thirds honest majority that achieves security in the presence of malicious adversariesat essentially the exact same cost as the best known protocols for semi-honest adversaries. Our construction is not a general transformation and thus it is possible that better semi-honest protocols will be constructed which do not support our transformation. Nevertheless, for the current state-of-the-art for many parties (based on Shamir sharing), our protocol invokes the best semi-honest multiplication protocol exactly once per multiplication gate (plus some additional local computation that is negligible to the overall cost). Concretely, the best version of our protocol requires each party to send on average of just 2 2/3 elements per multiplication gate (when the number of multiplication gates is at least the number of parties). This is four times faster than the previous-best protocol of Barak et al. (ACM CCS 2018) for small fields, and twice as fast as the previous-best protocol of Chida et al. (CRYPTO 2018) for large fields.
Secure multi-party computation (MPC) allows a set of parties to compute a function jointly while keeping their inputs private. Compared with the MPC based on garbled circuits, some recent research results show that MPC based on secret sharing (SS) works at a very high speed. Moreover, SS-based MPC can be easily vectorized and achieve higher throughput. In SS-based MPC, however, we need many communication rounds for computing concrete protocols like equality check, less-than comparison, etc. This property is not suited for large-latency environments like the Internet (or WAN). In this paper, we construct semi-honest secure communication-efficient two-party protocols. The core technique is Beaver triple extension, which is a new tool for treating multi-fan-in gates, and we also show how to use it efficiently. We mainly focus on reducing the number of communication rounds, and our protocols also succeed in reducing the number of communication bits (in most cases). As an example, we propose a less-than comparison protocol (under practical parameters) with three communication rounds. This is less than a half compared with the previous work. Moreover, the number of communication bits is also 38.4%38.4\%38.4% fewer. As a result, total online execution time is 56.1%56.1\%56.1% shorter than the previous work adopting the same settings. Although the computation costs of our protocols are more expensive than those of previous work, we confirm via experiments that such a disadvantage has small effects on the whole online performance in the typical WAN environments.