Paper 2017/189

Authenticated Garbling and Efficient Maliciously Secure Multi-Party Computation

Jonathan Katz and Samuel Ranellucci and Xiao Wang

Abstract

In this paper, we extend the recent work by Wang et al., who proposed a new framework for secure two-party computation in the preprocessing model that can be instantiated efficiently using TinyOT. We show that their protocol can be generalized to the multi-party setting, where the preprocessing functionality is based on the multi-party TinyOT-like protocol. Assuming there are $n$ parties where at most $n-1$ parties are corrupted, the function-dependent phase has a total communication complexity of $O(\kappa n^2)$ bits per AND gate; the online phase has a total communication complexity of $O(\kappa n^2)$ bits per input/output bit. In the second part of this paper, we propose a new multi-party TinyOT protocol. The new protocol uses a set of new techniques that allow parties to distributively check the correctness without the need for cut-and-choose. The resulting protocol is much more efficient compared to previous protocols: with statistical security parameter $\rho$, the complexity to generate one AND triple is $O(\frac{\rho}{\log |C|}n^2)$, where $|C|$ is the circuit size. The best previous multi-party TinyOT protocol by Frederiksen et al. has a complexity of $O(\frac{\rho^2}{\log^2|C|}n^2)$ per AND triple. The complexity is measured in terms of number of symmetric key operations/number of symmetric key messages. The resulting protocol enjoys extremely high efficiency, compared to the state-of-the-art protocol by Lindell et al. that combines the BMR protocol with the SPDZ protocol.