You are looking at a specific version 20210618:191314 of this paper. See the latest version.

Paper 2021/303

The More The Merrier: Reducing the Cost of Large Scale MPC

S. Dov Gordon and Daniel Starin and Arkady Yerukhimovich

Abstract

Secure multi-party computation (MPC) allows multiple parties to perform secure joint computations on their private inputs. Today, applications for MPC are growing with thousands of parties wishing to build federated machine learning models or trusted setups for blockchains. To address such scenarios we propose a suite of novel MPC protocols that maximize throughput when run with large numbers of parties. In particular, our protocols have both communication and computation complexity that decrease with the number of parties. Our protocols build on prior protocols based on packed secret-sharing, introducing new techniques to build more efficient computation for general circuits. Specifically, we introduce a new approach for handling linear attacks that arise in protocols using packed secret-sharing and we propose a method for unpacking shared multiplication triples without increasing the asymptotic costs. Compared with prior work, we avoid the $\log |C|$ overhead required when generically compiling circuits of size $|C|$ for use in a SIMD computation, and we improve over folklore ``committee-based'' solutions by a factor of $O(s)$, the statistical security parameter. In practice, our protocol is up to $10X$ faster than any known construction, under a reasonable set of parameters.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published by the IACR in EUROCRYPT 2021
Keywords
secure computationmalicious security
Contact author(s)
gordon @ gmu edu,dstarin @ peratonlabs com,arkady @ gwu edu
History
2022-05-26: last of 2 revisions
2021-03-09: received
See all versions
Short URL
https://ia.cr/2021/303
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.