In this article we present an implementation of general purpose secure twoparty computation framework offering security against semi-honest threat model. Proposed framework implements Yao’s garbled circuits protocol and incorporates novel oblivious transfer protocol based on white-box cryptography methods for the first time to avoid computationally expensive public key operations. Also experimental results illustrating the efficiency of our framework compared with previous implementations are provided.
In this article we present an implementation of general purpose secure twoparty computation framework offering security against semi-honest threat model. Proposed framework implements Yao’s garbled circuits protocol and incorporates novel oblivious transfer protocol based on white-box cryptography methods for the first time to avoid computationally expensive public key operations. Also experimental results illustrating the efficiency of our framework compared with previous implementations are provided.
Yao first introduced a constant-round protocol for secure two-party computation (2PC) withstanding semi-honest adversaries by using a tool called "garbled circuit". Later, many protocols based on garbled circuit approach have been presented, most of which discussed malicious adversaries and efficiency about 2PC. However, there only have a few protocols dealing with the fundamental property of fairness for Yao's garbled circuit approach, in which one involved a trusted third party and the others are very expensive. In the paper, we propose' an efficient Yao's garbled circuit protocol for fair secure 2PC based on ElGamal encryption, Pedersen commitment, Cachin et al.'s verifiable oblivious transfer and Ou-Ruan et al.'s gradual release homomorphic timed commitment. The protocol achieves two advantages: it doesn't need the third party and it is more efficient than other fair secure Yao's protocols.
Abstract. We show an efficient secure two-party protocol, based on Yao’s construction, which provides security against malicious adversaries. Yao’s original protocol is only secure in the presence of semi-honest adversaries. Security against malicious adversaries can be obtained by applying the compiler of Goldreich, Micali and Wigderson (the “GMW compiler”). However, this approach does not seem to be very practical as it requires using generic zero-knowledge proofs. Our construction is based on applying cut-and-choose techniques to the original circuit and inputs. Security is proved according to the ideal/real simulation paradigm, and the proof is in the standard model (with no random oracle model or common reference string assumptions). The resulting protocol is computationally efficient: the only usage of asymmetric cryptography is for running O(1) oblivious transfers for each input bit (or for each bit of a statistical security parameter, whichever is larger). Our protocol combines techniques from folklore (like cut-and-choose) along with new techniques for efficiently proving consistency of inputs. We remark that a naive implementation of the cut-and-choose technique with Yao’s protocol does not yield a secure protocol. This is the first paper to show how to properly implement these techniques, and to provide a full proof of security. Our protocol can also be interpreted as a constant-round black-box reduction of secure two-party com-putation to oblivious transfer and perfectly-hiding commitments, or a black-box reduction of secure two-party computation to oblivious transfer alone, with a number of rounds which is linear in a sta-tistical security parameter. These two reductions are comparable to Kilian’s reduction, which uses OT alone but incurs a number of rounds which is linear in the depth of the circuit [18]. 1
Many deployments of secure multi-party computation (MPC) in practice have used information-theoretic three-party protocols that tolerate a single, semi-honest corrupt party, since these protocols enjoy very high efficiency. We propose a new approach for secure three-party computation (3PC) that improves security while maintaining practical efficiency that is competitive with traditional information-theoretic protocols. Our protocol is based on garbled circuits and provides security against a single, malicious corrupt party. Unlike information-theoretic 3PC protocols, ours uses a constant number of rounds. Our protocol only uses inexpensive symmetric-key cryptography: hash functions, block ciphers, pseudorandom generators (in particular, no oblivious transfers) and has performance that is comparable to that of Yao’s (semi-honest) 2PC protocol. We demonstrate the practicality of our protocol with an implementation based on the JustGarble framework of Bellare et al. (S&P 2013). The implementation incorporates various optimizations including the most recent techniques for efficient circuit garbling. We perform experiments on several benchmarking circuits, in different setups. Our experiments confirm that, despite providing a more demanding security guarantee, our protocol has performance comparable to existing information-theoretic 3PC. 1
Secure two-party computation enables two parties to evaluate a function cooperatively without revealing to either party anything beyond the function's output. The garbled-circuit technique, a generic approach to secure two-party computation for semi-honest participants, was developed by Yao in the 1980s, but has been viewed as being of limited practical significance due to its inefficiency. We demonstrate several techniques for improving the running time and memory requirements of the garbled-circuit technique, resulting in an implementation of generic secure two-party computation that is significantly faster than any previously reported while also scaling to arbitrarily large circuits. We validate our approach by demonstrating secure computation of circuits with over 109 gates at a rate of roughly 10 microseconds per garbled gate, and showing order-of-magnitude improvements over the best previous privacy-preserving protocols for computing Hamming distance, Levenshtein distance, Smith-Waterman genome alignment, and AES.
In this thesis we design and implement three approaches to provide efficient Secure Two- Party Computation (2PC) protocols that are secure in presence of malicious adversaries. The field of secure two-party computation enables two mutually distrusting parties, each with their own private input, to run a computation of an arbitrary program. At the end of the computation, nothing about their private input is leaked except for what can be learned from the output of the computation. The seminal work of Yao in 1986 provided the first proof that such a computation is feasible using the so called garbled circuits and given an Oblivious Transfer protocol. In this thesis, we follow Yao’s garbled circuit approach and focus on efficient protocols that are secure against malicious adversaries. We examine three different categories of optimization. In each category, we present a 2PC protocol, prove its security, and implement it as a proof of concept to demonstrate its running time in practice. Non-interactive Secure Computation: In this category, we offer the first implementation of a malicious 2PC protocol that reduces the required rounds of interaction between the two parties to only two rounds (i.e., each party sends only one message to the other party). Mixed Secure Two-Party Computation: In the second category we target big and complex programs and break them into subprograms. Then, we compute each subprogram using the most efficient 2PC protocol that is suitable for it. Finally, we securely connect these subprograms together. The goal is to reduce the overhead of the garbled circuits significantly, which results in a more efficient overall 2PC protocol for programs with specific properties. Secure Computation for Random Access Machine Programs: In the third category, we target programs that require random access to the memory (as opposed to a sequential access). We present the first efficient maliciously-secure protocol for computing such programs.
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.