CryptoDB
An Efficient Protocol for Secure Two-Party Computation in the Presence of Malicious Adversaries
Authors: | |
---|---|
Download: | |
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, and can be transformed into a protocol that achieves security against malicious adversaries 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 {\sf 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 \emph{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 computation 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 statistical 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~\cite{Kil}. |
BibTeX
@misc{eprint-2008-17726, title={An Efficient Protocol for Secure Two-Party Computation in the Presence of Malicious Adversaries}, booktitle={IACR Eprint archive}, keywords={cryptographic protocols / secure two-party computation, efficiency}, url={http://eprint.iacr.org/2008/049}, note={An extended abstract appeared in Eurocrypt 2007. This is the full version lindell@cs.biu.ac.il 13908 received 30 Jan 2008}, author={Yehuda Lindell and Benny Pinkas}, year=2008 }