Cut-and-choose mechanisms

The cut-and-choose mechanism and ways to deal with input consistency, output authenticity, selective failure, two-output functionalities, etc., against malicious adversaries.

Category contains 9 papers:

[B13] Luís T. A. N. Brandão. Secure Two-Party Computation with Reusable Bit-Commitments, via a Cut-and-Choose with Forge-and-Lose Technique. Asiacrypt 2013 [pdf] [bibtex]

Summary: New cut-and-choose mechanism, achieving statistical security ⚠ {$2^{-s}$} only ⚠ {$\sim s$} garbled circuits. »

[FJNOO13] Tore Kasper Frederiksen, Thomas Pelle Jakobsen, Jesper Buus Nielsen, Peter Sebastian Nordholt, Claudio Orlandi . MiniLEGO: Efficient Secure Two-Party Computation. EUROCRYPT 2013 [pdf] [bibtex]

Summary: Improves upon the NO09? LEGO protocol construction by relying on standard assumptions. »

[KS06] Mehmet Kiraz, Berry Schoenmakers. A Protocol Issue for the Malicious Case of Garbled Circuit Construction. Information Theory in the Benelux 2006 [pdf]

Summary: Identifies and fixes an issue related to selective failure attacks in cut-and-choose protocols. »

[L13] Yehuda Lindell. Fast Cut-and-Choose Based Protocols for Malicious and Covert Adversaries. CRYPTO 2013 [pdf] [bibtex]

Summary: Presents a cut-and-choose mechanism requiring only ⚠ {$s$} garbled circuits for ⚠ {$2^{-s}$} security »

[LP07] Yehuda Lindell, Benny Pinkas. An Efficient Protocol for Secure Two-Party Computation in the Presence of Malicious Adversaries. EUROCRYPT 2007 [pdf] [bibtex]

Summary: The first cut-and-choose protocol with complete formal security proof »

[LP12] Yehuda Lindell, Benny Pinkas. Secure two-party computation via cut-and-choose oblivious transfer. J Cryptology 2012 [pdf] [bibtex]

Summary: Efficiency improvements to the cut-and-choose method, using a new abstraction of cut-and-choose OT. »

[MR13] Payman Mohassel, Ben Riva. Garbled Circuits Checking Garbled Circuits: More Efficient and Secure Two-Party Computation. CRYPTO 2013 [pdf] [bibtex]

Summary: Several new techniques giving efficiency improvements to cut-and-choose mechanisms »

[SS11] abhi shelat, Chih-Hao Shen. Two-Output Secure Computation with Malicious Adversaries. EUROCRYPT 2011 [pdf] [bibtex]

Summary: Several new techniques for malicious security in the cut-and-choose paradigm »

[SS13] abhi shelat, Chih-Hao Shen. Fast two-party secure computation with minimal assumptions. ACM CCS 2013 [pdf] [bibtex]

Summary: Achieves malicious-secure 2PC with linear overhead in the security parameter, from general assumptions »