International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Paper: An Efficient Protocol for Secure Two-Party Computation in the Presence of Malicious Adversaries

Authors:
Yehuda Lindell
Benny Pinkas
Download:
URL: http://eprint.iacr.org/2008/049
Search ePrint
Search Google
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
}