Cryptology ePrint Archive: Report 2016/944

High-Throughput Secure Three-Party Computation for Malicious Adversaries and an Honest Majority

Jun Furukawa and Yehuda Lindell and Ariel Nof and Or Weinstein

Abstract: In this paper, we describe a new protocol for secure three-party computation of any functionality, with an honest majority and a \textit{malicious} adversary. Our protocol has both an information-theoretic and computational variant, and is distinguished by extremely low communication complexity and very simple computation. We start from the recent semi-honest protocol of Araki et al. (ACM CCS 2016) in which the parties communicate only a single bit per AND gate, and modify it to be secure in the presence of malicious adversaries. Our protocol follows the paradigm of first constructing Beaver multiplication triples and then using them to verify that circuit gates are correctly computed. As in previous work (e.g., the so-called TinyOT and SPDZ protocols), we rely on the cut-and-choose paradigm to verify that triples are correctly constructed. We are able to utilize the fact that at most one of three parties is corrupted in order to construct an extremely simple and efficient method of constructing such triples. We also present an improved combinatorial analysis for this cut-and-choose which can be used to achieve improvements in other protocols using this approach.

Category / Keywords: cryptographic protocols / secure multiparty computation, malicious adversaries, honest majority

Original Publication (with minor differences): IACR-EUROCRYPT-2017

Date: received 29 Sep 2016, last revised 8 Feb 2017

Contact author: lindell at biu ac il

Available format(s): PDF | BibTeX Citation

Note: This is the full version of the EUROCRYPT 2017 paper.

Version: 20170208:105710 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]