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

Revisiting LEGOs: Optimizations, Analysis, and their Limit.

Yan Huang, Ruiyu Zhu

Published Jan 1, 2015• 2 citations
OpenAlex

Abstract

Abstract. The Cut-and-choose paradigm gives by far the most popular and efficient secure two-party computation protocols in the standard malicious model, able to offer s bits of security with only s copies of garbled circuits in the one-time execution scenario [33]. Nielsen, Orlandi et al. [48,13] have even proposed the seminal idea of LEGO-style cut-and-choose to further reduce the number of circuit copies to less than s while still keep constant round complexity. However, a substantial gap still exists between the theoretical idea of LEGO cut-and-choose and a practical implementation, e.g., [48] is not compatible with free-XOR and uses expensive asymmetric key operations for soldering, while [13] leaves the important building-block of soldering unspecified. In this work, we introduce XOR-Homomorphic Interactive Hash and propose an efficient implemen-tation of this primitive by combining Reed-Solomon encoding and k-out-of-n oblivious transfers. We show how to apply this primitive to solve the performance-critical wire-soldering problem and propose a new LEGO-style cut-and-choose protocol. Comparing to previous LEGO-style protocols, ours only requires a single (as opposed to “a majority of”) correctly garbled gate in each bucket to guarantee security against malicious adversaries. Plus, through integrating Half-Gates garbling, we double the chance a “bad ” gate being detected in the check stage (compared to MiniLEGO [13]). Our construction

Related papers

DUPLO

Vladimir Kolesnikov, Jesper Buus Nielsen, Mike Rosulek +2 more

Cut-and-choose (CC) is the standard approach to making Yao's garbled circuit two-party computation (2PC) protocol secure against malicious adversaries. Traditional cut-and-choose operates at the level of entire circuits, whereas the LEGO paradigm (Nielsen & Orlandi, TCC 2009) achieves asymptotic improvements by performing cut-and-choose at the level of individual gates. In this work we propose a unified approach called DUPLO that spans the entire continuum between these two extremes. The cut-and-choose step in our protocol operates on the level of arbitrary circuit "components," which can range in size from a single gate to the entire circuit itself.

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

DUPLO: Unifying Cut-and-Choose for Garbled Circuits.

Vladimir Kolesnikov, Jesper Buus Nielsen, Mike Rosulek +2 more

Cut-and-choose (CC) is the standard approach to making Yao's garbled circuit two-party computation (2PC) protocol secure against malicious adversaries. Traditional cut-and-choose operates at the level of entire circuits, whereas the LEGO paradigm (Nielsen & Orlandi, TCC 2009) achieves asymptotic improvements by performing cut-and-choose at the level of individual gates. In this work we propose a unified approach called DUPLO that spans the entire continuum between these two extremes. The cut-and-choose step in our protocol operates on the level of arbitrary circuit which can range in size from a single gate to the entire circuit itself. With this entire continuum of parameter values at our disposal, we find that the best way to scale 2PC to computations of realistic size is to use CC components of intermediate size, and not at the extremes. On computations requiring several millions of gates or more, our more general approach to CC gives between 4-7x improvement over existing approaches. In addition to our technical contributions of modifying and optimizing previous protocol techniques to work with general CC components, we also provide an extension of the recent Frigate circuit compiler (Mood et al, Euro S&P 2016) to effectively express any C-style program in terms of components which can be processed efficiently using our protocol.

•Jan 1, 2017•9 citations

Garbled Circuits Checking Garbled Circuits: More Efficient and Secure Two-Party Computation.

Payman Mohassel, Ben Riva

Applying cut-and-choose techniques to Yao’s garbled circuit protocol has been a promising approach for designing efficient Two-Party Computation (2PC) with malicious and covert security, as is evident from various optimizations and software implementations in the recent years. We revisit the security and efficiency properties of this popular approach and propose alternative constructions and definitions that are more suitable for use in practice. • We design an efficient fully-secure malicious 2PC protocol for two-output functions that only requires O(t|C|) symmetric-key operations (with small constant factors) where |C | is the circuit size and t is a statistical security parameter. This is essentially the optimal complexity for protocols based on cut-and-choose, resolving a main question left open by the previous work on the subject. Our protocol utilizes novel techniques for enforcing garbler’s input consistency and handling twooutput functions that are more efficient than all prior solutions. • Motivated by the goal of eliminating the all-or-nothing nature of 2PC with covert security (that privacy and correctness are fully compromised if the adversary is not caught in the challenge phase), we propose a new security definition for 2PC that strengthens the guarantees provided by the standard

•Jan 1, 2013•0 citations

Cut-and-Choose Bilateral Oblivious Transfer and Its Application in Secure Two-party Computation.

Han Jiang, Xiaochao Wei, Chuan Zhao +1 more

Abstract. In secure two-party computation protocols, the cut-and-choose paradigm is used to prevent the malicious party who constructs the garbled circuits from cheating. In previous realization of the cut-and-choose technique on the garbled circuits, the delivery of the random keys is divided into multiple stages. Thus, the round complexity is high and the consistency of cut-and-choose challenge should be proved. In this paper, we introduce a new primitive called cut-and-choose bilateral oblivious transfer, which transfers all necessary keys of garbled circuits in one process. Specifically, in our oblivious transfer protocol, the sender inputs two pairs (x0, x1), (y0, y1) and a bit τ; the receiver inputs two bits σ and j. After the protocol execution, the receiver obtains xτ, yσ for j = 1, and x0, x1, y0, y1 for j = 0. By the introduction of this new primitive, the round complexity of secure two-party computation protocol can be decreased; the cut-and-choose challenge j is no need to be opened anymore, therefore the consistency proof of j is omitted. In addition, the primitive is of independent interest and could be useful in many cut-and-choose scenarios.

•Jan 1, 2014•0 citations

Amortizing Garbled Circuits

Yan Huang, Jonathan I. Katz, Vladimir Kolesnikov +2 more

Abstract. We consider secure two-party computation in a multiple-execution setting, where two parties wish to securely evaluate the same circuit multiple times. We design efficient garbled-circuit-based two-party protocols secure against malicious adversaries. Recent works by Lindell (Crypto 2013) and Huang-Katz-Evans (Crypto 2013) have obtained op-timal complexity for cut-and-choose performed over garbled circuits in the single execution setting. We show that it is possible to obtain much lower amortized overhead for cut-and-choose in the multiple-execution setting. Our efficiency improvements result from a novel way to combine a recent technique of Lindell (Crypto 2013) with LEGO-based cut-and-choose techniques (TCC 2009, Eurocrypt 2013). In concrete terms, for 40-bit statistical security we obtain a 2 × improvement (per execution) in com-munication and computation for as few as 7 executions, and require only 8 garbled circuits (i.e., a 5 × improvement) per execution for as low as 3500 executions. Our results suggest the exciting possibility that secure two-party computation in the malicious setting can be less than an order of magnitude more expensive than in the semi-honest setting. 1

Lecture notes in computer science•Aug 17, 2014•2 citations

Fast Cut-and-Choose Bilateral Oblivious Transfer for Malicious Adversaries

Xiaochao Wei, Han Jiang, Chuan Zhao +2 more

In secure two-party computation protocols based on garbled circuit, oblivious transfer (OT) plays an important role in transferring the garbled keys of the participants. In addition to the traditional OT primitive, many other variants of OT have also been presented, such as outsourced oblivious transfer (OOT), cut-and-choose oblivious transfer (CCOT), cut-and-choose bilateral oblivious transfer (CCBOT), etc. These new primitives significantly improve the efficiency and feasibility of secure two-party computation protocols, mainly in optimising computational complexity and interactive rounds. Among these primitives, CCBOT proposed by Zhao et al. in TrustCom 2015 is a novel one and helps to minimize the round complexity of the outer secure two-party computation protocols. In addition, they constructed a CCBOT protocol based on homomorphic encryption scheme in the malicious model. However, their protocol uses the cut-and-choose technique to guarantee security against malicious adversaries, as a result the protocol has an error probability. The commitment scheme is also inevitably involved in their protocol. In this paper, we present a CCBOT protocol with the security against malicious adversaries based on the Decisional Diffie-Hellman (DDH) assumption. Our proposed protocol avoids using the cut-and-choose technique and commitment scheme. In terms of efficiency, our protocol is much more efficient than the previous protocol.

IEEE International Conference on Trust, Security and Privacy in Computing and Communications (TrustCom)•Aug 1, 2016•12 citations
Abstract. The Cut-and-choose paradigm gives by far the most popular and efficient secure two-party computation protocols in the standard malicious model, able to offer s bits of security with only s copies of garbled circuits in the one-time execution scenario [33]. Nielsen, Orlandi et al. [48,13] have even proposed the seminal idea of LEGO-style cut-and-choose to further reduce the number of circuit copies to less than s while still keep constant round complexity. However, a substantial gap still exists between the theoretical idea of LEGO cut-and-choose and a practical implementation, e.g., [48] is not compatible with free-XOR and uses expensive asymmetric key operations for soldering, while [13] leaves the important building-block of soldering unspecified. In this work, we introduce XOR-Homomorphic Interactive Hash and propose an efficient implemen-tation of this primitive by combining Reed-Solomon encoding and k-out-of-n oblivious transfers. We show how to apply this primitive to solve the performance-critical wire-soldering problem and propose a new LEGO-style cut-and-choose protocol. Comparing to previous LEGO-style protocols, ours only requires a single (as opposed to “a majority of”) correctly garbled gate in each bucket to guarantee security against malicious adversaries. Plus, through integrating Half-Gates garbling, we double the chance a “bad ” gate being detected in the check stage (compared to MiniLEGO [13]). Our construction
Cut-and-choose (CC) is the standard approach to making Yao's garbled circuit two-party computation (2PC) protocol secure against malicious adversaries. Traditional cut-and-choose operates at the level of entire circuits, whereas the LEGO paradigm (Nielsen & Orlandi, TCC 2009) achieves asymptotic improvements by performing cut-and-choose at the level of individual gates. In this work we propose a unified approach called DUPLO that spans the entire continuum between these two extremes. The cut-and-choose step in our protocol operates on the level of arbitrary circuit "components," which can range in size from a single gate to the entire circuit itself.
Cut-and-choose (CC) is the standard approach to making Yao's garbled circuit two-party computation (2PC) protocol secure against malicious adversaries. Traditional cut-and-choose operates at the level of entire circuits, whereas the LEGO paradigm (Nielsen & Orlandi, TCC 2009) achieves asymptotic improvements by performing cut-and-choose at the level of individual gates. In this work we propose a unified approach called DUPLO that spans the entire continuum between these two extremes. The cut-and-choose step in our protocol operates on the level of arbitrary circuit which can range in size from a single gate to the entire circuit itself. With this entire continuum of parameter values at our disposal, we find that the best way to scale 2PC to computations of realistic size is to use CC components of intermediate size, and not at the extremes. On computations requiring several millions of gates or more, our more general approach to CC gives between 4-7x improvement over existing approaches. In addition to our technical contributions of modifying and optimizing previous protocol techniques to work with general CC components, we also provide an extension of the recent Frigate circuit compiler (Mood et al, Euro S&P 2016) to effectively express any C-style program in terms of components which can be processed efficiently using our protocol.
Applying cut-and-choose techniques to Yao’s garbled circuit protocol has been a promising approach for designing efficient Two-Party Computation (2PC) with malicious and covert security, as is evident from various optimizations and software implementations in the recent years. We revisit the security and efficiency properties of this popular approach and propose alternative constructions and definitions that are more suitable for use in practice. • We design an efficient fully-secure malicious 2PC protocol for two-output functions that only requires O(t|C|) symmetric-key operations (with small constant factors) where |C | is the circuit size and t is a statistical security parameter. This is essentially the optimal complexity for protocols based on cut-and-choose, resolving a main question left open by the previous work on the subject. Our protocol utilizes novel techniques for enforcing garbler’s input consistency and handling twooutput functions that are more efficient than all prior solutions. • Motivated by the goal of eliminating the all-or-nothing nature of 2PC with covert security (that privacy and correctness are fully compromised if the adversary is not caught in the challenge phase), we propose a new security definition for 2PC that strengthens the guarantees provided by the standard
Abstract. In secure two-party computation protocols, the cut-and-choose paradigm is used to prevent the malicious party who constructs the garbled circuits from cheating. In previous realization of the cut-and-choose technique on the garbled circuits, the delivery of the random keys is divided into multiple stages. Thus, the round complexity is high and the consistency of cut-and-choose challenge should be proved. In this paper, we introduce a new primitive called cut-and-choose bilateral oblivious transfer, which transfers all necessary keys of garbled circuits in one process. Specifically, in our oblivious transfer protocol, the sender inputs two pairs (x0, x1), (y0, y1) and a bit τ; the receiver inputs two bits σ and j. After the protocol execution, the receiver obtains xτ, yσ for j = 1, and x0, x1, y0, y1 for j = 0. By the introduction of this new primitive, the round complexity of secure two-party computation protocol can be decreased; the cut-and-choose challenge j is no need to be opened anymore, therefore the consistency proof of j is omitted. In addition, the primitive is of independent interest and could be useful in many cut-and-choose scenarios.
Abstract. We consider secure two-party computation in a multiple-execution setting, where two parties wish to securely evaluate the same circuit multiple times. We design efficient garbled-circuit-based two-party protocols secure against malicious adversaries. Recent works by Lindell (Crypto 2013) and Huang-Katz-Evans (Crypto 2013) have obtained op-timal complexity for cut-and-choose performed over garbled circuits in the single execution setting. We show that it is possible to obtain much lower amortized overhead for cut-and-choose in the multiple-execution setting. Our efficiency improvements result from a novel way to combine a recent technique of Lindell (Crypto 2013) with LEGO-based cut-and-choose techniques (TCC 2009, Eurocrypt 2013). In concrete terms, for 40-bit statistical security we obtain a 2 × improvement (per execution) in com-munication and computation for as few as 7 executions, and require only 8 garbled circuits (i.e., a 5 × improvement) per execution for as low as 3500 executions. Our results suggest the exciting possibility that secure two-party computation in the malicious setting can be less than an order of magnitude more expensive than in the semi-honest setting. 1
In secure two-party computation protocols based on garbled circuit, oblivious transfer (OT) plays an important role in transferring the garbled keys of the participants. In addition to the traditional OT primitive, many other variants of OT have also been presented, such as outsourced oblivious transfer (OOT), cut-and-choose oblivious transfer (CCOT), cut-and-choose bilateral oblivious transfer (CCBOT), etc. These new primitives significantly improve the efficiency and feasibility of secure two-party computation protocols, mainly in optimising computational complexity and interactive rounds. Among these primitives, CCBOT proposed by Zhao et al. in TrustCom 2015 is a novel one and helps to minimize the round complexity of the outer secure two-party computation protocols. In addition, they constructed a CCBOT protocol based on homomorphic encryption scheme in the malicious model. However, their protocol uses the cut-and-choose technique to guarantee security against malicious adversaries, as a result the protocol has an error probability. The commitment scheme is also inevitably involved in their protocol. In this paper, we present a CCBOT protocol with the security against malicious adversaries based on the Decisional Diffie-Hellman (DDH) assumption. Our proposed protocol avoids using the cut-and-choose technique and commitment scheme. In terms of efficiency, our protocol is much more efficient than the previous protocol.