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

Lecture notes in computer science

Fast Optimistically Fair Cut-and-Choose 2PC

Alptekın Küpçü, Payman Mohassel

Published Jan 1, 2017• 4 citations
Publisher
DOI
10.1007/978-3-662-54970-4_12

Related papers

Richer Efficiency/Security Trade-offs in 2PC

Vladimir Kolesnikov, Payman Mohassel, Ben Riva +1 more

Lecture notes in computer science•Jan 1, 2015•12 citations

Blazing Fast 2PC in the Offline/Online Setting with Security for Malicious Adversaries.

Yehuda Lindell, Ben Riva

Recently, several new techniques were presented to dramatically improve key parts of secure two-party computation (2PC) protocols that use the cut-and-choose paradigm on garbled cir-cuits for 2PC with security against malicious adversaries. These include techniques for reducing the number of garbled circuits (Lindell 13, Huang et al. 13, Lindell and Riva 14, Huang et al. 14) and techniques for reducing the overheads besides garbled circuits (Mohassel and Riva 13, Shen and Shelat 13). We design a highly optimized protocol in the offline/online setting that makes use of all state-of-the-art techniques, along with several new techniques that we introduce. A crucial part of our protocol is a new technique for enforcing consistency of the inputs used by the party who garbles the circuits. This technique has both theoretical and practical advantages over previous methods. We present a prototype implementation of our new protocol, which is also the first imple-mentation of the amortized cut-and-choose technique of Lindell and Riva (Crypto 2014). Our prototype achieves a speed of just 7 ms in the online stage and just 74 ms in the offline stage per 2PC invoked, for securely computing AES in the presence of malicious adversaries (using 9 threads on two 2.9GHz machines located in the same Amazon region). We note that no prior work has gone below one second overall on average for the secure computation of AES for mali-cious adversaries (nor below 20ms in the online stage). Our implementation securely evaluates SHA-256 (which is a much bigger circuit) with 33 ms online time and 206 ms offline time, per 2PC invoked. 1

•Jan 1, 2015•5 citations

Weak Parity

Scott Aaronson, Andris Ambainis, Kaspars Balodis +1 more

Lecture notes in computer science•Jan 1, 2014•3 citations

Blazing Fast 2PC in the Offline/Online Setting with Security for Malicious Adversaries

Yehuda Lindell, Ben Riva

Recently, several new techniques were presented to dramatically improve key parts of secure two-party computation (2PC) protocols that use the cut-and-choose paradigm on garbled circuits for 2PC with security against malicious adversaries. These include techniques for reducing the number of garbled circuits (Lindell 13, Huang et al. 13, Lindell and Riva 14, Huang et al. 14) and techniques for reducing the overheads besides garbled circuits (Mohassel and Riva 13, Shen and Shelat~13). We design a highly optimized protocol in the offline/online setting that makes use of all state-of-the-art techniques, along with several new techniques that we introduce. A crucial part of our protocol is a new technique for enforcing consistency of the inputs used by the party who garbles the circuits. This technique has both theoretical and practical advantages over previous methods.

ACM SIGSAC Conference on Computer and Communications Security (CCS)•Oct 6, 2015•66 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 a new definition that are more suitable for use in practice. • We design an efficient fully-secure 2PC protocol for two-output functions that only requires O(t|C|) symmetric-key operations (with small constant factors, and ignoring factors that are independent of the circuit in use) in the Random Oracle Model, 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 covert model, and offers a smoother security vs. efficiency tradeoff to protocol designers in choosing the right deterrence factor. In our new notion, correctness is always guaranteed, privacy is fully guaranteed with probability (1 − ɛ), and with probability ɛ (i.e. the event of undetected cheating), privacy is only “partially compromised ” with at most a single bit of information leaked, in case of an abort. We present two efficient 2PC constructions achieving our new notion. Both protocols are competitive with the previous covert 2PC protocols based on cut-and-choose. A distinct feature of the techniques we use in all our constructions is to check consistency of inputs and outputs using new gadgets that are themselves garbled circuits, and to verify validity of these gadgets using multi-stage cut-and-choose openings.

•Jan 1, 2013•0 citations

Upper Bounds and Parity Considerations

Harry A. Mavromatis

Springer eBooks•Jan 1, 1987•0 citations
Recently, several new techniques were presented to dramatically improve key parts of secure two-party computation (2PC) protocols that use the cut-and-choose paradigm on garbled cir-cuits for 2PC with security against malicious adversaries. These include techniques for reducing the number of garbled circuits (Lindell 13, Huang et al. 13, Lindell and Riva 14, Huang et al. 14) and techniques for reducing the overheads besides garbled circuits (Mohassel and Riva 13, Shen and Shelat 13). We design a highly optimized protocol in the offline/online setting that makes use of all state-of-the-art techniques, along with several new techniques that we introduce. A crucial part of our protocol is a new technique for enforcing consistency of the inputs used by the party who garbles the circuits. This technique has both theoretical and practical advantages over previous methods. We present a prototype implementation of our new protocol, which is also the first imple-mentation of the amortized cut-and-choose technique of Lindell and Riva (Crypto 2014). Our prototype achieves a speed of just 7 ms in the online stage and just 74 ms in the offline stage per 2PC invoked, for securely computing AES in the presence of malicious adversaries (using 9 threads on two 2.9GHz machines located in the same Amazon region). We note that no prior work has gone below one second overall on average for the secure computation of AES for mali-cious adversaries (nor below 20ms in the online stage). Our implementation securely evaluates SHA-256 (which is a much bigger circuit) with 33 ms online time and 206 ms offline time, per 2PC invoked. 1
Recently, several new techniques were presented to dramatically improve key parts of secure two-party computation (2PC) protocols that use the cut-and-choose paradigm on garbled circuits for 2PC with security against malicious adversaries. These include techniques for reducing the number of garbled circuits (Lindell 13, Huang et al. 13, Lindell and Riva 14, Huang et al. 14) and techniques for reducing the overheads besides garbled circuits (Mohassel and Riva 13, Shen and Shelat~13). We design a highly optimized protocol in the offline/online setting that makes use of all state-of-the-art techniques, along with several new techniques that we introduce. A crucial part of our protocol is a new technique for enforcing consistency of the inputs used by the party who garbles the circuits. This technique has both theoretical and practical advantages over previous methods.
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 a new definition that are more suitable for use in practice. • We design an efficient fully-secure 2PC protocol for two-output functions that only requires O(t|C|) symmetric-key operations (with small constant factors, and ignoring factors that are independent of the circuit in use) in the Random Oracle Model, 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 covert model, and offers a smoother security vs. efficiency tradeoff to protocol designers in choosing the right deterrence factor. In our new notion, correctness is always guaranteed, privacy is fully guaranteed with probability (1 − ɛ), and with probability ɛ (i.e. the event of undetected cheating), privacy is only “partially compromised ” with at most a single bit of information leaked, in case of an abort. We present two efficient 2PC constructions achieving our new notion. Both protocols are competitive with the previous covert 2PC protocols based on cut-and-choose. A distinct feature of the techniques we use in all our constructions is to check consistency of inputs and outputs using new gadgets that are themselves garbled circuits, and to verify validity of these gadgets using multi-stage cut-and-choose openings.