In FOCS 1986, Yao presented a constant-round secure computation protocol for two-party computation that is secure in the presence of semi-honest adversaries. In this paper, we show how to efficiently transform Yao's protocol so that the result is secure in the presence of malicious adversaries. Security is proved according to the ideal/real simulation paradigm.
Our protocol does not use zero-knowledge proofs (unlike the compiler of Goldreich, Micali and Wigderson). In addition, the only asymmetric cryptography used is for running $s$ (or less) oblivious transfers for each input bit, where $s$ is a statistical security parameter.
Furthermore, even though the resulting protocol provides security according to a simulation based definition, the oblivious transfer protocol that it uses can satisfy a more relaxed security definition: it is only required to provide simulation based security in the face of a corrupt receiver; and provide privacy alone in the face of a corrupt sender.
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.
Joint work with Yehuda Lindell.
Audio (MP3 File, Podcast Ready)
Copyright. All Rights Reserved.