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

The Herald of the Siberian State University of Telecommunications and Information Science

Passive secure three-party computation with an honest majority

Sergey Mihailovich Ratseev, Ольга Ивановна Череватенко

Published Mar 21, 2025• 0 citations
Publisher

Abstract

In 2016, the authors Araki T., Furukawa J., Lindell Y., Of A. and Ohara K. introduced a new information-theoretic protocol (and a computationally-secure variant) for secure three- party computation with an honest majority. The protocol has very minimal computation and communication. The authors did not provide a complete protocols. This paper provides complete protocols for secure multiparty computation.

DOI
10.55648/1998-6920-2025-19-1-45-53

Related papers

High-Throughput Semi-Honest Secure Three-Party Computation with an Honest Majority

Toshinori Araki, Jun Furukawa, Yehuda Lindell +2 more

In this paper, we describe a new information-theoretic protocol (and a computationally-secure variant) for secure three-party computation with an honest majority. The protocol has very minimal computation and communication; for Boolean circuits, each party sends only a single bit for every AND gate (and nothing is sent for XOR gates). Our protocol is (simulation-based) secure in the presence of semi-honest adversaries, and achieves privacy in the client/server model in the presence of malicious adversaries. On a cluster of three 20-core servers with a 10Gbps connection, the implementation of our protocol carries out over 1.3 million AES computations per second, which involves processing over 7 billion gates per second. In addition, we developed a Kerberos extension that replaces the ticket-granting-ticket encryption on the Key Distribution Center (KDC) in MIT-Kerberos with our protocol, using keys/ passwords that are shared between the servers. This enables the use of Kerberos while protecting passwords. Our implementation is able to support a login storm of over 35,000 logins per second, which suffices even for very large organizations. Our work demonstrates that high-throughput secure computation is possible on standard hardware.

ACM SIGSAC Conference on Computer and Communications Security (CCS)•Oct 24, 2016•414 citations

An Efficient Passive-to-Active Compiler for Honest-Majority MPC over Rings.

Mark Abspoel, Anders Dalskov, Daniel E. Escudero +1 more

Multiparty computation (MPC) over rings such as \(\mathbb {Z}_{2^{32}}\) or \(\mathbb {Z}_{2^{64}}\) has received a great deal of attention recently due to its ease of implementation and attractive performance. Several actively secure protocols over these rings have been implemented, for both the dishonest majority setting and the setting of three parties with one corruption. However, in the honest majority setting, no concretely efficient protocol for arithmetic computation over rings has yet been proposed that allows for an arbitrary number of parties.

•Jan 1, 2019•3 citations

Efficient Three-party Computation: An Information-theoretic Approach from Cut-and-Choose

Zhili Chen

As far as we know, the literature on secure computation from cut-and-choose has focused on achieving computational security against malicious adversaries. It is unclear whether the idea of cut-and-choose can be adapted to secure computation with information-theoretic security. In this work we explore the possibility of using cut-and-choose in information theoretic setting for secure three-party computation (3PC). Previous work on 3PC has mainly focus on the semi-honest case, and is motivated by the observation that real-word deployments of multi-party computation (MPC) seem to involve few parties. We propose a new protocol for information-theoretically secure 3PC tolerating one malicious party with cheating probability $2^{-s}$ using $s$ runs of circuit computation in the cut-and-choose paradigm. The computational cost of our protocol is essentially only a small constant worse than that of state-of-the-art 3PC protocols against a semi-honest corruption, while its communication round is greatly reduced compared to other maliciously secure 3PC protocols in information-theoretic setting.

arXiv:1908.03718•Aug 10, 2019•1 citation

Optimizing Semi-Honest Secure Multiparty Computation for the Internet

Aner Ben-Efraim, Yehuda Lindell, Eran Omri

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.

ACM SIGSAC Conference on Computer and Communications Security (CCS)•Oct 24, 2016•92 citations

Fast and Secure Three-party Computation

Payman Mohassel, Mike Rosulek, Ye Zhang

Many deployments of secure multi-party computation (MPC) in practice have used information-theoretic three-party protocols that tolerate a single, semi-honest corrupt party, since these protocols enjoy very high efficiency. We propose a new approach for secure three-party computation (3PC) that improves security while maintaining practical efficiency that is competitive with traditional information-theoretic protocols. Our protocol is based on garbled circuits and provides security against a single, malicious corrupt party. Unlike information-theoretic 3PC protocols, ours uses a constant number of rounds. Our protocol only uses inexpensive symmetric-key cryptography: hash functions, block ciphers, pseudorandom generators (in particular, no oblivious transfers) and has performance that is comparable to that of Yao's (semi-honest) 2PC protocol.

ACM SIGSAC Conference on Computer and Communications Security (CCS)•Oct 6, 2015•112 citations

TurboPack

Daniel E. Escudero, Vipul Goyal, Antigoni Polychroniadou +1 more

We present a novel approach to honest majority secure multiparty computation in the preprocessing model with information theoretic security that achieves the best online communication complexity. The online phase of our protocol requires 12 elements in total per multiplication gate with circuit-dependent preprocessing, or 20 elements in total with circuit-independent preprocessing. Prior works achieved linear online communication complexity in n, the number of parties, with the best prior existing solution involving 1.5n elements per multiplication gate. Only one recent work packing [28] achieves constant online communication complexity, but the constants are large (108 elements for passive security, and twice that for active security). That said, our protocol offers a very efficient information theoretic online phase for any number of parties.

ACM SIGSAC Conference on Computer and Communications Security (CCS)•Nov 7, 2022•29 citations
In 2016, the authors Araki T., Furukawa J., Lindell Y., Of A. and Ohara K. introduced a new information-theoretic protocol (and a computationally-secure variant) for secure three- party computation with an honest majority. The protocol has very minimal computation and communication. The authors did not provide a complete protocols. This paper provides complete protocols for secure multiparty computation.
In this paper, we describe a new information-theoretic protocol (and a computationally-secure variant) for secure three-party computation with an honest majority. The protocol has very minimal computation and communication; for Boolean circuits, each party sends only a single bit for every AND gate (and nothing is sent for XOR gates). Our protocol is (simulation-based) secure in the presence of semi-honest adversaries, and achieves privacy in the client/server model in the presence of malicious adversaries. On a cluster of three 20-core servers with a 10Gbps connection, the implementation of our protocol carries out over 1.3 million AES computations per second, which involves processing over 7 billion gates per second. In addition, we developed a Kerberos extension that replaces the ticket-granting-ticket encryption on the Key Distribution Center (KDC) in MIT-Kerberos with our protocol, using keys/ passwords that are shared between the servers. This enables the use of Kerberos while protecting passwords. Our implementation is able to support a login storm of over 35,000 logins per second, which suffices even for very large organizations. Our work demonstrates that high-throughput secure computation is possible on standard hardware.
Multiparty computation (MPC) over rings such as Z232\mathbb {Z}_{2^{32}}Z232​ or Z264\mathbb {Z}_{2^{64}}Z264​ has received a great deal of attention recently due to its ease of implementation and attractive performance. Several actively secure protocols over these rings have been implemented, for both the dishonest majority setting and the setting of three parties with one corruption. However, in the honest majority setting, no concretely efficient protocol for arithmetic computation over rings has yet been proposed that allows for an arbitrary number of parties.
As far as we know, the literature on secure computation from cut-and-choose has focused on achieving computational security against malicious adversaries. It is unclear whether the idea of cut-and-choose can be adapted to secure computation with information-theoretic security. In this work we explore the possibility of using cut-and-choose in information theoretic setting for secure three-party computation (3PC). Previous work on 3PC has mainly focus on the semi-honest case, and is motivated by the observation that real-word deployments of multi-party computation (MPC) seem to involve few parties. We propose a new protocol for information-theoretically secure 3PC tolerating one malicious party with cheating probability 2−s2^{-s}2−s using sss runs of circuit computation in the cut-and-choose paradigm. The computational cost of our protocol is essentially only a small constant worse than that of state-of-the-art 3PC protocols against a semi-honest corruption, while its communication round is greatly reduced compared to other maliciously secure 3PC protocols in information-theoretic setting.
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.
Many deployments of secure multi-party computation (MPC) in practice have used information-theoretic three-party protocols that tolerate a single, semi-honest corrupt party, since these protocols enjoy very high efficiency. We propose a new approach for secure three-party computation (3PC) that improves security while maintaining practical efficiency that is competitive with traditional information-theoretic protocols. Our protocol is based on garbled circuits and provides security against a single, malicious corrupt party. Unlike information-theoretic 3PC protocols, ours uses a constant number of rounds. Our protocol only uses inexpensive symmetric-key cryptography: hash functions, block ciphers, pseudorandom generators (in particular, no oblivious transfers) and has performance that is comparable to that of Yao's (semi-honest) 2PC protocol.
We present a novel approach to honest majority secure multiparty computation in the preprocessing model with information theoretic security that achieves the best online communication complexity. The online phase of our protocol requires 12 elements in total per multiplication gate with circuit-dependent preprocessing, or 20 elements in total with circuit-independent preprocessing. Prior works achieved linear online communication complexity in n, the number of parties, with the best prior existing solution involving 1.5n elements per multiplication gate. Only one recent work packing [28] achieves constant online communication complexity, but the constants are large (108 elements for passive security, and twice that for active security). That said, our protocol offers a very efficient information theoretic online phase for any number of parties.