Yao Garbled Circuits are a known solution for the secure multi-party computation problem. However, it’s poor performance prevents the use of garbled circuits in a real life applications. In this report we propose a protocol for secure multi-party computation that uses Yao Garbled Circuits for Sharemind. Subtle details of existing Sharemind protocols allow us to implement essential parts of the Yao Circuit Evaluation (YCE) differently from general implementations. This approach could lead to a better performance result of YCE and offer a general way of adding new internal functionality of Sharemind.
Yao Garbled Circuits are a known solution for the secure multi-party computation problem. However, it’s poor performance prevents the use of garbled circuits in a real life applications. In this report we propose a protocol for secure multi-party computation that uses Yao Garbled Circuits for Sharemind. Subtle details of existing Sharemind protocols allow us to implement essential parts of the Yao Circuit Evaluation (YCE) differently from general implementations. This approach could lead to a better performance result of YCE and offer a general way of adding new internal functionality of Sharemind.
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
Secure two-party computation problem is about two parties that want to compute some function of their private inputs in a way that other party won’t learn it. We describe a general way to perform secure two-party computation of a function specified as a boolean circuit, which was proposed by A.A. Yao in 1982. This method is named Yao garbled circuit evaluation and is secure against semi-honest adversaries. We present a new efficient protocol for secure two-party computation Circus, that is secure against malicious adversary in consistency model. Consistency model implies that either both parties will receive correct output and persist privacy of their inputs or a honest party will know, that is was cheated and that adversary potentially have learnt 1 bit of other party’s input value. We specify all necessary sub-protocols and their security requirements and prove security of Circus in malicious environment.
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.
Zero-knowledge protocols are one of the fundamental concepts in modern cryptography and have countless applications. However, after more than 30 years from their introduction, there are only very few languages (essentially those with a group structure) for which we can construct zero-knowledge protocols that are efficient enough to be used in practice. In this paper we address the problem of how to construct efficient zero-knowledge protocols for generic languages and we propose a protocol based on Yao’s garbled circuit technique. The motivation for our work is that in many cryptographic applications it is useful to be able to prove efficiently statements of the form e.g., “I know x s.t. y = SHA-256(x)” for a common input y (or other “unstructured” languages), but no efficient protocols for this task are currently known. It is clear that zero-knowledge is a subset of secure two-party computation (i.e., any protocol for generic secure computation can be used to do zero-knowledge). The main contribution of this paper is to construct an efficient protocol for the special case of secure two-party computation where only one party has input (like in the zero-knowledge case). The protocol achieves active security and is essentially only twice as slow as the passive secure version of Yao’s garbled circuit protocol. This is a great improvement with respect to the cut-n-choose technique to make Yao’s protocol actively secure, where the complexity grows linearly with the security parameter.