A NEW PARADIGM FOR PRACTICAL MALICIOUSLY SECURE MULTI-PARTY COMPUTATION

Undergraduate

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 pre-processing 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.


Introduction

Protocols for secure multi-party computation (MPC) allow a set of mutually distrusting parties to jointly compute an agreed upon function on their own inputs. The security of MPC protocols ensures that no party can learn any information about other parties’ inputs except the output. The past ten years have witnessed a huge improvement on the concrete efficiency of MPC protocols. Numerous companies have been founded using MPC to solve real-life problems that cannot be solved otherwise. For example, Dyadic  uses MPC to help secure cryptographic keys; Sharemind uses MPC to process financial d and prevent satellites from colliding without disclosing trajectories; Partisia uses MPC for privacypreserving auctions.

While these results are impressive, the semi-honest security model is used in almost all applications, which assumes that both parties follow the protocol honestly yet may try to learn additional information from the execution. This is clearly not sufficient for all applications and has motivated researchers to construct protocols achieving the stronger notion of malicious security, where the adversary can cheat in arbitrary ways. Malicious protocols provide strong security but come with a very high performance penalty. Indeed, the state-of-the-art protocol with malicious security in 2014  is still orders of magnitude slower than the protocols in the semi-honest setting.

This thesis introduces a new paradigm for constructing maliciously secure MPC protocols with extremely high efficiency. Existing protocols for MPC can be categorized into two main classes: 1) protocols based on garbled circuits that require high bandwidth but only a constant number of roundtrips;

2) protocols based on secret-sharing that usually need less communication but number of roundtrips proportional to the circuit depth. Such a trade-off between throughput and latency seems difficult to avoid especially for concretely efficient protocols. Authenticated garbling is a new paradigm that shows how to integrate these two classes of protocols efficiently such that the communication is only marginally increased compared to the secret-sharing protocols, while achieving constant-round.


Two-party Computation

Protocols for generic 2PC in the semi-honest setting based on Yao’s garbled-circuit protocol have seen tremendous efficiency improvements over the past several years.

Cut-and-choose is one of the most popular approach to strengthen the garbled circuit protocol with malicious security. For statistical security 2ρ, the best approaches using this paradigm require ρ garbled circuits (which is optimal). The cut-and-choose approach incurs significant overhead, especially for large circuits, precisely because ρ garbled circuits need to be transmitted (typically, ρ ≥ 40). In order to mitigate this, recent works have explored secure computation in an amortized setting where the same function is evaluated multiple times (on different inputs).

When amortizing over τ executions, only) garbled circuits are needed per execution. More recently, Nielsen and Orlandi proposed a protocol with constant amortized overhead, but only when τ is at least the number of gates in the circuit.

Other techniques for constant-round, maliciously secure two-party computation in the single-execution setting, with asymptotically better performance than circuit-level cut-and-choose, have also been explored. The LEGO protocol and subsequent optimizations are based on a gate-level cut-and-choose subroutine that can be carried out during a preprocessing phase before the circuit to be evaluated is known. This class of protocols has good asymptotic performance and small online time; however, the best reported implementation of LEGO still has a higher overall running time than the best protocol based on a circuit-level cut-and-choose approach.