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 Asia Conference on Computer and Communications Security (ASIA CCS)

MYao: Efficient Multiparty “Yao” Garbled Circuits with Row Reduction and Half Gates

Aner Ben-Efraim, Lior Breitman, Jonathan Bronshtein, Olga V. Nissenbaum, Eran Omri

Published Jun 1, 2026• 0 citations
Publisher

Abstract

Garbled circuits are a powerful and important cryptographic primitive, introduced by Yao [FOCS 1986] for secure two-party computation. Beaver, Micali and Rogaway (BMR) [STOCS 1990] extended the garbled circuit technique to construct the first constant-round secure multiparty computation (MPC) protocol. In the BMR protocol, the garbled circuit size grows linearly and the online computation time grows quadratically with the number of parties. Previous solutions to avoid this relied on key-homomorphic PRFs, incurring a large garbled circuit size and slow online computation time.

DOI
10.1145/3779208.3785262

Related papers

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

Berekening op Beveiligd Data: in alle vormen

Oliver Zajonc

MPC is a primitive which allows for mutually distrusting parties to jointly compute the output of a function over their private inputs. This technology has many practical applications and, as such, has seen extensive research, which has generated several different methods for achieving MPC. In this thesis, we discuss and expand on three of the best known methods for achieving MPC. The first is based on Shamir's secret sharing scheme. We present a novel secret sharing based scheme which achieves MPC under the following constraints. We allow for a malicious adversary that can arbitrarily delay any parties for a number of rounds. While these parties are delayed they can neither send nor receive messages. Furthermore, we assume that all messages between the parties are sent via a set of central parties called Relays. We provide a UC functionality and protocol for the relays, and for the MPC protocol. The second is based on Yao's garbled circuits protocol. Here we expand on the row reduction technology already present in maliciously secure two party garbled circuits and show how to achieve similar results in the multiparty setting. This reduces the number of ciphertexts that must be sent per AND gate in the multiparty Garbled Circuits setting from four to three. The third is based on Fully Homomorphic Encryption. The particular protocol we introduce expands the FINAL FHE scheme and expands it to accept multiple keys, which can then be used by different parties to collectively outsource a computation to an untrusted server. We cover the various different obstacles that needed to be overcome in this expansion, and we show that our protocol has an asymptotic improvement in the efficiency of the bootstrapping over other multi-key FHE schemes. This now requires a number of polynomial multiplications which is linear in the number parties, rather than quadratic.

•Jun 18, 2026•0 citations

Efficient Fair Secure Two-Party Computation

Ou Ruan, Zhou Jing, Minghui Zheng +1 more

Yao first introduced a constant-round protocol for secure two-party computation (2PC) withstanding semi-honest adversaries by using a tool called "garbled circuit". Later, many protocols based on garbled circuit approach have been presented, most of which discussed malicious adversaries and efficiency about 2PC. However, there only have a few protocols dealing with the fundamental property of fairness for Yao's garbled circuit approach, in which one involved a trusted third party and the others are very expensive. In the paper, we propose' an efficient Yao's garbled circuit protocol for fair secure 2PC based on ElGamal encryption, Pedersen commitment, Cachin et al.'s verifiable oblivious transfer and Ou-Ruan et al.'s gradual release homomorphic timed commitment. The protocol achieves two advantages: it doesn't need the third party and it is more efficient than other fair secure Yao's protocols.

IEEE Asia-Pacific Services Computing Conference (APSCC)•Dec 1, 2012•5 citations

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•95 citations

Equivocating Yao: constant-round adaptively secure multiparty computation in the plain model

Ran Canetti, Oxana Poburinnaya, Muthuramakrishnan Venkitasubramaniam

Yao's circuit garbling scheme is one of the basic building blocks of cryptographic protocol design. Originally designed to enable two-message, two-party secure computation, the scheme has been extended in many ways and has innumerable applications. Still, a basic question has remained open throughout the years: Can the scheme be extended to guarantee security in the face of an adversary that corrupts both parties, adaptively, as the computation proceeds?

ACM Symposium on Theory of Computing (STOC)•Jun 15, 2017•14 citations

Garbled Protocols and Two-Round MPC from Bilinear Maps

Sanjam Garg, Akshayaram Srinivasan

In this paper, we initiate the study of garbled protocols - a generalization of Yao's garbled circuits construction to distributed protocols. More specifically, in a garbled protocol construction, each party can independently generate a garbled protocol component along with pairs of input labels. Additionally, it generates an encoding of its input. The evaluation procedure takes as input the set of all garbled protocol components and the labels corresponding to the input encodings of all parties and outputs the entire transcript of the distributed protocol. We provide constructions for garbling arbitrary protocols based on standard computational assumptions on bilinear maps (in the common random string model). Next, using garbled protocols we obtain a general compiler that compresses any arbitrary round multiparty secure computation protocol into a two-round UC secure protocol. Previously, two-round multiparty secure computation protocols were only known assuming witness encryption or learning-with errors. Benefiting from our generic approach we also obtain protocols (i) for the setting of random access machines (RAM programs) while keeping communication and computational costs proportional to running times, while (ii) making only a black-box use of the underlying group, eliminating the need for any expensive non-black-box group operations. Our results are obtained by a simple but powerful extension of the non-interactive zero-knowledge proof system of Groth, Ostrovsky and Sahai [Journal of ACM, 2012].

Annual Symposium on Foundations of Computer Science•Oct 1, 2017•52 citations
Garbled circuits are a powerful and important cryptographic primitive, introduced by Yao [FOCS 1986] for secure two-party computation. Beaver, Micali and Rogaway (BMR) [STOCS 1990] extended the garbled circuit technique to construct the first constant-round secure multiparty computation (MPC) protocol. In the BMR protocol, the garbled circuit size grows linearly and the online computation time grows quadratically with the number of parties. Previous solutions to avoid this relied on key-homomorphic PRFs, incurring a large garbled circuit size and slow online computation time.
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.
MPC is a primitive which allows for mutually distrusting parties to jointly compute the output of a function over their private inputs. This technology has many practical applications and, as such, has seen extensive research, which has generated several different methods for achieving MPC. In this thesis, we discuss and expand on three of the best known methods for achieving MPC. The first is based on Shamir's secret sharing scheme. We present a novel secret sharing based scheme which achieves MPC under the following constraints. We allow for a malicious adversary that can arbitrarily delay any parties for a number of rounds. While these parties are delayed they can neither send nor receive messages. Furthermore, we assume that all messages between the parties are sent via a set of central parties called Relays. We provide a UC functionality and protocol for the relays, and for the MPC protocol. The second is based on Yao's garbled circuits protocol. Here we expand on the row reduction technology already present in maliciously secure two party garbled circuits and show how to achieve similar results in the multiparty setting. This reduces the number of ciphertexts that must be sent per AND gate in the multiparty Garbled Circuits setting from four to three. The third is based on Fully Homomorphic Encryption. The particular protocol we introduce expands the FINAL FHE scheme and expands it to accept multiple keys, which can then be used by different parties to collectively outsource a computation to an untrusted server. We cover the various different obstacles that needed to be overcome in this expansion, and we show that our protocol has an asymptotic improvement in the efficiency of the bootstrapping over other multi-key FHE schemes. This now requires a number of polynomial multiplications which is linear in the number parties, rather than quadratic.
Yao first introduced a constant-round protocol for secure two-party computation (2PC) withstanding semi-honest adversaries by using a tool called "garbled circuit". Later, many protocols based on garbled circuit approach have been presented, most of which discussed malicious adversaries and efficiency about 2PC. However, there only have a few protocols dealing with the fundamental property of fairness for Yao's garbled circuit approach, in which one involved a trusted third party and the others are very expensive. In the paper, we propose' an efficient Yao's garbled circuit protocol for fair secure 2PC based on ElGamal encryption, Pedersen commitment, Cachin et al.'s verifiable oblivious transfer and Ou-Ruan et al.'s gradual release homomorphic timed commitment. The protocol achieves two advantages: it doesn't need the third party and it is more efficient than other fair secure Yao's protocols.
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.
In this paper, we initiate the study of garbled protocols - a generalization of Yao's garbled circuits construction to distributed protocols. More specifically, in a garbled protocol construction, each party can independently generate a garbled protocol component along with pairs of input labels. Additionally, it generates an encoding of its input. The evaluation procedure takes as input the set of all garbled protocol components and the labels corresponding to the input encodings of all parties and outputs the entire transcript of the distributed protocol. We provide constructions for garbling arbitrary protocols based on standard computational assumptions on bilinear maps (in the common random string model). Next, using garbled protocols we obtain a general compiler that compresses any arbitrary round multiparty secure computation protocol into a two-round UC secure protocol. Previously, two-round multiparty secure computation protocols were only known assuming witness encryption or learning-with errors. Benefiting from our generic approach we also obtain protocols (i) for the setting of random access machines (RAM programs) while keeping communication and computational costs proportional to running times, while (ii) making only a black-box use of the underlying group, eliminating the need for any expensive non-black-box group operations. Our results are obtained by a simple but powerful extension of the non-interactive zero-knowledge proof system of Groth, Ostrovsky and Sahai [Journal of ACM, 2012].