International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Jun Furukawa

Publications

Year
Venue
Title
2023
JOFC
High-Throughput Secure Three-Party Computation with an Honest Majority
In the setting of secure multiparty computation, a set of parties wish to carry out a joint computation of their inputs while keeping them private. In this paper, we describe new information-theoretic protocols for secure three-party computation with an honest majority. Our protocols compute Boolean circuits with minimal computation and communication. We start with a protocol, based on replicated secret sharing, which is secure in the presence of semi-honest adversaries in which the parties communicate only a single bit per AND gate. Then, we show how to modify it to be secure in the presence of malicious adversaries. Our malicious 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. Then, we provide general techniques for improving efficiency of cut-and-choose protocols on multiplication triples and utilize them to further improve the protocol. The resulting protocol for malicious adversaries has bandwidth of only 7 bits per AND gate per party, when amortizing over 1 million gates and with statistical error $$2^{-40}$$ 2 - 40 . An implementation of our protocol achieves a throughput of over 7 billion AND gates per second with the semi-honest protocol, and over 1 billion AND gates per second with the malicious protocol (using the above parameters). Our results demonstrate that high-throughput secure computation is possible.
2017
EUROCRYPT
2006
ASIACRYPT
2004
ASIACRYPT
2004
PKC
2001
CRYPTO

Program Committees

Asiacrypt 2023
Asiacrypt 2020
Asiacrypt 2019
Asiacrypt 2009