Paper 2016/944

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

Jun Furukawa, Yehuda Lindell, 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.

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

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
A minor revision of an IACR publication in EUROCRYPT 2017
Keywords
secure multiparty computationmalicious adversarieshonest majority
Contact author(s)
lindell @ biu ac il
History
2017-12-14: last of 2 revisions
2016-10-01: received
See all versions
Short URL
https://ia.cr/2016/944
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/944,
      author = {Jun Furukawa and Yehuda Lindell and Ariel Nof and Or Weinstein},
      title = {High-Throughput Secure Three-Party Computation for Malicious Adversaries and an Honest Majority},
      howpublished = {Cryptology ePrint Archive, Paper 2016/944},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/944}},
      url = {https://eprint.iacr.org/2016/944}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.