Techniques for Efficient Secure Computation Based on Yao’s Protocol

Ashish Choudhury, Arpita Patra

Yehuda Lindell, Benny Pinkas B

Ou Ruan, Cai Fu, Zhou Jing +2 more

With the development of modern Internet and ad hoc networks, there is an increasing need for autonomous entities cooperating together to perform knowledge-and information-based decision making. Data in its original form, however, typically contains sensitive information about individuals and unmanaged data exchange may violate individual privacy. Secure multi-party computation is proposed to solve this problem and has become a hot topic. Yao's garbled circuit approach is a major method in designing protocols for secure two-party computation. However, only few papers dealt with the fundamental property of fairness for Yao's garbled circuit protocol, in which one introduced a third party and others were based on cut-and-choose techniques that are inherently expensive. In this paper, we propose an efficient fair UC-secure Yao's garbled circuit protocol in the malicious model based on Jarecki et al.'s construction and Ou Ruan et al.'s gradual release commitment. The protocol avoids involving any third party or using cut-and-choose techniques, and it is more bandwidth-efficient than other Yao-based protocols. Furthermore, its security could be proved within the UC framework.

Marek Jawurek, Florian Kerschbaum, Claudio Orlandi

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.

Ronald Cramer

Yehuda Lindell, Benny Pinkas B

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