A New Paradigm for Practical Maliciously Secure Multi-Party Computation

Abstract

Secure Multi-Party Computation (MPC) protocols allow a group of mutually distrusting users to compute a function jointly on their inputs without revealing any information beyond the output. For many years, implementations of MPC protocols have targeted security against semi-honest adversaries, i.e., attackers are assumed to execute the protocol honestly but try to learn private information after the fact. Protocols secure against stronger and more realistic malicious adversaries, who could behave arbitrarily during the protocol execution, were known to exist but were much less efficient.

This thesis introduces a new paradigm to construct extremely efficient MPC protocols with malicious security. In particular, this thesis consists of three major contributions.

1. We introduce the authenticated garbling framework, and present an efficient concrete instantiation of the protocol. The resulting protocol partially closes the gap between semi-honest and malicious MPC protocols asymptotically; the implementation of the protocol represents the state-of-the-art system for malicious two-party computation.

2. We discuss how to apply authenticated garbling to the multi-party setting, where all-but-one parties can be corrupted by the adversary. The resulting protocol improves upon the best previous constant-round protocol by orders of magnitude. We also present a system that, for the first time, enables MPC executions among hundreds of parties, distributed globally.

3. We present a series of optimizations to two-party authenticated garbling by interpreting authenticated garbling in a new way. The improved malicious protocol has essentially the same concrete efficiency as the best semi-honest protocol in the preprocessing model.

4. We develop these protocols in EMP-toolkit, a practical and efficient MPC tool that can be used to build new protocols and to develop applications using our existing protocols.