caa a22 4500 606148930 CHVBK 20210128100531.0 cr unu---uuuuu 210128e20150401xx s 000 0 eng 10.1007/s00145-014-9177-x doi (NATIONALLICENCE)springer-10.1007/s00145-014-9177-x An Efficient Protocol for Secure Two-Party Computation in the Presence of Malicious Adversaries [Elektronische Daten] [Yehuda Lindell, Benny Pinkas] 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 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)$$ 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 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(20th STOC, 1988) reduction, which uses OT alone but incurs a number of rounds which is linear in the depth of the circuit. International Association for Cryptologic Research, 2014 Secure two-party computation nationallicence Yao's protocol nationallicence Real/ideal simulation paradigm nationallicence Security against malicious adversaries nationallicence Lindell Yehuda Department of Computer Science, Bar-Ilan University, Ramat Gan, Israel aut Pinkas Benny Department of Computer Science, Bar-Ilan University, Ramat Gan, Israel aut Journal of Cryptology Springer US; http://www.springer-ny.com 28/2(2015-04-01), 312-350 0933-2790 28:2<312 2015 28 145 https://doi.org/10.1007/s00145-014-9177-x text/html Onlinezugriff via DOI BK010053 XK010053 XK010000 Metadata rights reserved Springer special CC-BY-NC licence nationallicence 1 research-article jats NATIONALLICENCE NATIONALLICENCE NL-springer NATIONALLICENCE 856 40 https://doi.org/10.1007/s00145-014-9177-x text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Lindell Yehuda Department of Computer Science, Bar-Ilan University, Ramat Gan, Israel aut NATIONALLICENCE 700 1- Pinkas Benny Department of Computer Science, Bar-Ilan University, Ramat Gan, Israel aut NATIONALLICENCE 773 0- Journal of Cryptology Springer US; http://www.springer-ny.com 28/2(2015-04-01), 312-350 0933-2790 28:2<312 2015 28 145