Fast Cut-and-Choose Based Protocols for Malicious and Covert Adversaries.

Yehuda Lindell

Published Jan 1, 2013• 0 citations

Abstract

In the setting of secure two-party computation, two parties wish to securely compute a joint function of their private inputs, while revealing only the output. One of the primary techniques for achieving efficient secure two-party computation is that of Yao’s garbled circuits (FOCS 1986). In the semi-honest model, where just one garbled circuit is constructed and evaluated, Yao’s protocol has proven itself to be very efficient. However, a malicious adversary who constructs the garbled circuit may construct a garbling of a different circuit computing a different function, and this cannot be detected (due to the garbling). In order to solve this problem, many circuits are sent and some of them are opened to check that they are correct while the others are evaluated. This methodology, called cut-and-choose, introduces significant overhead, both in computation and in communication, and is mainly due to the number of circuits that must be used in order to prevent cheating. In this paper, we present a cut-and-choose protocol for secure computation based on garbled circuits, with security in the presence of malicious adversaries, that vastly improves on all previous protocols of this type. Concretely, for a cheating probability of at most 2−40, the best previous works send between 125 and 128 circuits. In contrast, in our protocol 40 circuits alone suffice (with some additional overhead). Asymptotically, we achieve a cheating probability of 2−s where s is the number of garbled circuits, in contrast to the previous best of 2−0.32s. We achieve this by introducing a new cut-and-choose methodology with the property that in order to cheat, all of the evaluated circuits must be incorrect, and not just the majority as in previous works. The security of our protocol relies on the Decisional Diffie-Hellman assumption.

Related papers

Cut-and-Choose Based Two-Party Computation in the Online/Offline and Batch Settings.

Yehuda Lindell, Ben Riva

Protocols for secure two-party computation enable a pair of mistrusting parties to compute a joint function of their private inputs without revealing anything but the output. One of the fundamental techniques for obtaining secure computation is that of Yao’s garbled circuits. In the setting of malicious adversaries, where the corrupted party can follow any arbitrary (polynomial-time) strategy in an attempt to breach security, the cut-and-choose technique is used to ensure that the garbled circuit is constructed correctly. The cost of this technique is the construction and transmission of multiple circuits; specifically, s garbled circuits are used in order to obtain a maximum cheating probability of 2−s. In this paper, we show how to reduce the amortized cost of cut-and-choose based secure two-party computation to O s logN garbled circuits when N secure computations are run. We use this method to construct a secure protocol in the batch setting. Next, we show how the cut-

Jan 1, 20140 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, 20130 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 scienceAug 17, 20142 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, 201612 citations

A Novel Bilateral Oblivious Transfer Protocol Based on Cut-and-Choose Technique

Lulu Ning, Jian Wang

The Yao's protocol based on garbled circuits is the foundation of secure two-party computation protocols, and Oblivious Transfer (OT), as a important tool in modern cryptography, plays a crucial role in transmitting garbled keys in the Yao's protocol. In the past decades, considerable attentions have been paid to the Cut-and-Choose technique which is applied to OT protocols to prevent malicious P1(called circuit generator) from constructing wrong garbled circuits. Additionally, Bilateral OT becomes a focus point, which can simultaneously transmit P1's and P2's (called circuit evaluator) garbled keys to guarantee input consistency of two parties and improve transmission efficiency. As can be seen, some Cut-and-Choose Bilateral OT (CCBOT) protocols have been proposed. Since CCBOT has emerged, the probability of malicious P1constructing wrong garbled circuits without being found becomes lower and the input consistency problem is properly resolved too. However, the security of most CCBOT protocols are facing challenges since they are based on the Decisional Diffie-Hellman (DDH) assumption, Quadratic Residues (QR) assumption and Decisional Composite Residuosity (DCR) assumption. In this paper, we present a novel CCBOT protocol with the security against malicious adversaries based on the Computational Diffie-Hellman (CDH) assumption, and analysize the correctness, efficiency and security of the constructed protocol. Besides, we analysize the cheating probability of P1in the CCBOT and extend the CCBOT to Single-Choice CCBOT to make the protocol more applicable.

Dec 1, 20201 citation

Secure Two-Party Computation via Cut-and-Choose Oblivious Transfer.

Yehuda Lindell, Benny Pinkas B

Protocols for secure two-party computation enable a pair of parties to compute a function of their inputs while preserving security properties such as privacy, correctness and independence of inputs. Recently, a number of protocols have been proposed for the efficient construction of two-party computation secure in the presence of malicious adversaries (where security is proven under the standard simulation-based ideal/real model paradigm for defining security). In this paper, we present a protocol for this task that follows the methodology of using cut-and-choose to boost Yao’s protocol to be secure in the presence of malicious adversaries. Relying on specific assumptions (DDH), we construct a protocol that is significantly more efficient and far simpler than the protocol of Lindell and Pinkas (Eurocrypt 2007) that follows the same methodology. We provide an exact, concrete analysis of the efficiency of our scheme and demonstrate that (at least for not very small circuits) our protocol is more efficient than any other known today. secure two-party computation, malicious adversaries, cut-and-choose, concrete effi-Keywords: ciency An extended abstract of this work appeared at TCC 2011.

Jan 1, 20103 citations