# More Efficient MPC from Improved Triple Generation and Authenticated Garbling

Kang Yang, Xiao Wang, Jiang Zhang

Research output: Chapter in Book/Report/Conference proceedingConference contribution

10 Scopus citations

## Abstract

Recent works on distributed garbling have provided highly efficient solutions for constant-round MPC tolerating an arbitrary number of corruptions. In this work, we improve upon state-of-the-art protocols in this paradigm for further performance gain. First, we propose a new protocol for generating authenticated AND triples, which is a key building block in many recent works. \beginitemize \item We propose a new authenticated bit protocol in the two-party and multi-party settings from bare IKNP OT extension, allowing us to reduce the communication by about $24%$ and eliminate many computation bottlenecks. We further improve the computational efficiency for multi-party authenticated AND triples with cheaper and fewer consistency checks and fewer hash function calls. \item We implemented our triple generation protocol and observe around $4\times$ to $5\times$ improvement compared to the best prior protocol in most settings. For example, in the two-party setting with 10 Gbps network and 8 threads, our protocol can generate more than $4$ million authenticated triples per second, while the best prior implementation can only generate $0.8$ million triples per second. In the multi-party setting, our protocol can generate more than $37000$ triples per second over 80 parties, while the best prior protocol can only generate the same number of triples per second over 16 parties. \enditemize We also improve the state-of-the-art multi-party authenticated garbling protocol. \beginitemize \item 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?$ bits per gate per garbler, where ? is the computational security parameter. This optimization is also applicable in the semi-honest multi-party setting. \item We further reduce the communication of circuit authentication from $4?$ bits to $1$ bit per gate, using a new multi-party batched circuit authentication, where ? is the statistical security parameter. Prior solution with similar efficiency is only applicable in the two-party setting. \enditemize For example, in the three-party setting, our techniques can lead to roughly a $35%$ reduction in the size of a distributed garbled circuit.

Original language English (US) CCS 2020 - Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security Association for Computing Machinery 1627-1646 20 9781450370899 https://doi.org/10.1145/3372297.3417285 Published - Oct 30 2020 27th ACM SIGSAC Conference on Computer and Communications Security, CCS 2020 - Virtual, Online, United StatesDuration: Nov 9 2020 → Nov 13 2020

### Publication series

Name Proceedings of the ACM Conference on Computer and Communications Security 1543-7221

### Conference

Conference 27th ACM SIGSAC Conference on Computer and Communications Security, CCS 2020 United States Virtual, Online 11/9/20 → 11/13/20

## Keywords

• malicious security
• secure computation

## ASJC Scopus subject areas

• Software
• Computer Networks and Communications

## Fingerprint

Dive into the research topics of 'More Efficient MPC from Improved Triple Generation and Authenticated Garbling'. Together they form a unique fingerprint.