Paper 2019/1104

More Efficient MPC from Improved Triple Generation and Authenticated Garbling

Kang Yang and Xiao Wang and Jiang Zhang

Abstract

Recent works on distributed garbling have provided highly efficient solutions for constant-round MPC protocols tolerating an arbitrary number of malicious corruptions. In this work, we improve upon state-of-the-art protocols in this paradigm for further performance gain. We improve the protocol for generating authenticated AND triples, which plays a crucial role in many recent works. -- We propose a multi-party authenticated bit protocol from bare IKNP OT extension, allowing us to 1) reduce the communication by $\approx 24\%$ with a small harmless leakage, and 2) eliminate many computation-heavy procedures like bit-matrix multiplications and consistency checks. This improvement also applies to the two-party setting. -- We reduce the cost of consistency check for multi-party authenticated shares by $\rho$ times where $\rho$ is the statistical security parameter, and also cut the number of hash function calls per party by a factor of $2\times$ when computing leaky authenticated AND triples. We further improve the state-of-the-art multi-party authenticated garbling protocol. -- We take the first step towards applying half-gates in the multi-party setting, which enables us to reduce the size of garbled tables by $2\kappa$ bits per AND gate per garbler, where $\kappa$ is the computational security parameter. This optimization is also applicable in the semi-honest multi-party setting. -- We further reduce the size of garbled tables by about $4\rho$ bits per AND gate, by using an almost universal hash function to perform the circuit authentication in a batch. Prior solution with similar efficiency is only applicable in the two-party setting. Along with other optimization, we reduce the communication complexity of the whole protocol (including both function-independent and function-dependent preprocessing phases that require the most resources) by $\approx 24\%$ and significantly improve the overall computational efficiency.