Cryptology ePrint Archive: Report 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.

Category / Keywords: cryptographic protocols / Multi-party computation; Authenticated AND triples; Distributed garbling

Date: received 26 Sep 2019

Contact author: yangk at sklc org,wangxiao@cs northwestern edu,jiangzhang09@gmail com

Available format(s): PDF | BibTeX Citation

Version: 20190929:184200 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]