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?
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?
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? We answer this question in the affirmative. We define a new type of symmetric encryption, called functionally equivocal encryption (FEE), and show that when Yao's scheme is implemented with FEE as the underlying encryption mechanism, it becomes secure against such adaptive adversaries. We then show how to implement FEE from any one-way function. Combining our scheme with noncommitting encryption, we obtain the first two-message, two-party computation protocol, and the first constant-round multiparty computation protocol, in the plain model, that are secure against semihonest adversaries who can adaptively corrupt all parties. Using standard techniques, this protocol can be made standalone secure against malicious corruptions in the plain model and universal composability secure in the common random string model. Additional applications include the first fully leakage-tolerant general multiparty computation protocol (with preprocessing), as well as a public-key version of FEE which can serve as a replacement for noncommitting encryption with better efficiency than what is possible for the latter.
A garbling scheme is used to garble a circuit C and an input x in a way that reveals the output C(x) but hides everything else. In many settings, the circuit can be garbled off-line without strict efficiency constraints, but the input must be garbled very efficiently on-line, with much lower complexity than evaluating the circuit. Yao’s scheme has essentially optimal on-line complexity, but only achieves selective security, where the adversary must choose the input x prior to seeing the garbled circuit. It has remained an open problem to achieve adaptive security, where the adversary can choose x after seeing the garbled circuit, while preserving on-line efficiency. In this work, we modify Yao’s scheme in a way that allows us to prove adaptive security under one-way functions. As our main instantiation, we get a scheme where the on-line complexity is only proportional to the width w of the circuit, which corresponds to the space complexity of the computation, but is independent of the circuit’s depth d. Alternately, we can also get an instantiation where the on-line complexity is only proportional to the input/output size and the depth d of the circuit but independent of its width w, albeit in this case we incur a 2 security loss in our reduction. More broadly, we relate the on-line complexity of adaptively secure garbling schemes in our framework to a certain type of pebble complexity of the circuit. As our main tool, of independent interest, we develop a new notion of somewhere equivocal encryption, which allows us to efficiently equivocate on a small subset of the message bits. ∗This work was done in part while some of the authors were visiting the Simons Institute for the Theory of Computing, supported by the Simons Foundation and by the DIMACS/Simons Collaboration in Cryptography through NSF grant CNS1523467. †University of Pennsylvania. Department of Computer Science. fbrett@cis.upenn.edu ‡Northeastern University. Department of Computer Science. zahra@ccs.neu.edu §University of California, Los Angeles. Department of Computer Science and Mathematics. rafail@cs.ucla.edu Research supported in part by NSF grants 09165174, 1065276, 1118126 and 1136174, US-Israel BSF grant 2008411, OKAWA Foundation Research Award, IBM Faculty Research Award, Xerox Faculty Research Award, B. John Garrick Foundation Award, Teradata Research Award, and Lockheed-Martin Corporation Research Award. This material is based upon work supported in part by DARPA Safeware program. The views expressed are those of the author and do not reflect the official policy or position of the Department of Defense or the U.S. Government. ¶Boston University and Northeastern University. Department of Computer Science. scafuro@bu.edu Research supported by NSF grants 1012798. ‖Northeastern University. Department of Computer Science. wichs@ccs.neu.edu. Research supported by NSF grants CNS-1347350, CNS-1314722, CNS-1413964.
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. Secure multi-party computation has been considered by the cryptographic community for a number of years. Until recently it has been a purely theoretical area, with few implementations with which to test various ideas. This has led to a number of optimisations being proposed which are quite restricted in their application. In this paper we describe an implementation of the two-party case, using Yao’s garbled circuits, and present various algorithmic protocol improvements. These optimisations are analysed both theoretically and empirically, using experiments of various adversarial situations. Our experimental data is provided for reasonably large circuits, including one which performs an AES encryption, a problem which we discuss in the context of various possible applications. 1
Abstract. We propose a new two-party computation protocol using Yao’s garbled circuits, which is secure in the case of malicious behavior. To illustrate the need for the new protocol, we first discuss security issues of three existing protocols for secure two-party computation using garbled circuits, in the case of malicious behavior. The first is a protocol by Pinkas (Eurocrypt 2003), and the other two are the committed-input scheme and the k-leaked model, both presented by Mohassel and Franklin (PKC 2006). We address security flaws in all schemes, which allow leaking of information on the private inputs. In the k-leaked model leaking of some information is permitted if a participant is cheating, but then the honest participant should be aware of it. We show that this is not the case. After discussing these security issues of the known schemes, we describe our new protocol. It is based on the protocol by Pinkas, and the correction of the flaw of the scheme by Pinkas makes our protocol not only more secure, but also more efficient. We provide a detailed informal security analysis of our new protocol. Keywords: Secure two-party computation, Yao’s garbled circuit, active adversary 1
Consider several parties that do not trust each other, yet they wish to correctly compute some common function of their local inputs while keeping these inputs private. This problem is known as "Secure Multi-Party Computation", and was introduced by Andrew Yao in 1982. Secure multi-party computations have some real world examples like electronic auctions, electronic voting or fingerprinting. In this thesis we consider the case where there are only two parties involved. This is known as "Secure Two-Party Computation". If there is a trusted third party called Carol, then the problem is pretty straightforward. The participating parties could hand their inputs in Carol who can compute the common function correctly and could return the outputs to the corresponding parties. The goal is to achieve (almost) the same result when there is no trusted third party. Cryptographic protocols are designed in order to solve these kinds of problems. These protocols are analyzed within an appropriate model in which the behavior of parties is structured. The basic level is called the Semi-Honest Model where parties are assumed to follow the protocol specification, but later can derive additional information based on the messages which have been received so far. A more realistic model is the so-called Malicious Model. The common approach is to first analyze a protocol in the semi-honest model and then later extend it into the malicious model. Any cryptographic protocol for secure two-party computation must satisfy the following security requirements: correctness, privacy and fairness. It must guarantee the correctness of the result while preserving the privacy of the parties’ inputs, even if one of the parties is malicious and behaves arbitrarily throughout the protocol. It must also guarantee fairness. This roughly means that whenever a party aborts the protocol prematurely, he or she should not have any advantage over the other party in discovering the output. The main question for researchers is to construct new protocols that achieve the above mentioned goals for secure multi-party computation. Of course, such protocols must be secure in a given model, as well as be as efficient as possible. In 1986, Yao presented the first general protocol for secure two-party computation which was applicable only to the semi-honest model. He uses a tool called "Garbled Circuit". Yao’s protocol uses the underlying primitives ("Pseudorandom Generator" and "Oblivious Transfer") as blackboxes which lead to efficient results. After Yao’s work many variants and improvements have been proposed for the malicious model. In this thesis, we design several new protocols for secure two-party computation based on Yao’s garbled circuit. Before we present the details of our new designs, we first show several weaknesses, security flaws or problems with the existing protocols in the literature. We first work in the semi-honest model and then extend it into the malicious model by presenting new protocols. Finally we add fairness to our protocol. Oblivious transfer (OT) is a fundamental primitive in modern cryptography which is useful for implementing protocols for secure multi-party computation. We study several variants of oblivious transfer in this thesis. We present a new protocol for the so-called "Committed OT". This protocol is very efficient in the sense that it is quite good in comparison to the most efficient committed OT protocols in the literature. The abovementioned flaw with the use of OT can be fixed with our committed oblivious transfer protocol. Furthermore, it is more general than all previous protocols, and, therefore, it is of independent interest. We also deal with fairness in this thesis. For protocols based on garbled circuit, so far only Benny Pinkas has presented a protocol in the literature for achieving fairness. We show a subtle problem with this protocol where the privacy of the inputs of one party can be compromised. We also describe this problem in detail which is in fact related to the fairness, and finally propose a more efficient scheme that does achieve fairness.