On Large-Scale Multiparty Computation with sub-linear Communication using Ephemeral Servers

Secure Multiparty Computation (MPC) is a technology that enables a set of mutually distrustful parties to securely compute a function on their inputs, without leaking any information about these inputs, beyond what is inferred from the output of the function. MPC is a useful tool in settings where it is unacceptable to rely on a trusted third-party to compute the function on behalf of the parties. This includes settings where data privacy is desirable (e.g. private auctions) but also in places where law and regulation (e.g. GDPR, CCPA, LGPD) would otherwise prevent such data from being subject to computation. The study of MPC protocols dates back to the seminal work of Andrew Yao (FOCS, 1986) and has garnered significant attention from cryptography researchers exploring new techniques, added efficiency, and inherent limitations of MPC protocols.
The emergence of large-scale permissionless networks such as Bitcoin and Ethereum has driven new interest in specific branches of MPC research aimed at combining the input-privacy of MPC with the resilience and scalability of modern blockchain networks. This would allow a set of limited clients to outsource a computation to “the blockchain” without revealing their inputs aka. MPC-as-a-Service. However, existing MPC protocols are designed to thrive when executed in the context of static and homogenous networks with high availability and low-latency communication and this makes them incompatible with the heterogenous and dynamic nature of permissionless networks. Moreover, the communication complexity of these protocols scales quadratically with the number of parties making them prohibitively expensive to execute at this scale.
Recent work of Gentry et al. (CRYPTO, 2021) proposed a model for MPC with the goal of identifying MPC protocols that overcome the above challenges. Such protocols are executed by a set of small randomly-selected committees and only allow each committee member to send a single message. Hence, the name: YOSO (You Only Speak Once) model. They also presented actual YOSO MPC protocols with statistical and computational security but left the question of establishing the underlying communication channels to future committee members largely unanswered.
This thesis provides a rigorous treatment of the problem of sending secret messages to future committee members. We provide a definitional framework around our main primitive - Encryption to the Future - and propose concrete constructions improving on existing protocols for establishing communication channels in the YOSO model. In addition, these existing protocols are not amenable to new efficient techniques for publicly verifiable resharing which is a key primitive when designing MPC protocols in the YOSO model. We
observe that our framework naturally generalizes to settings where these efficient techniques are applicable by taking advantage of the underlying additive homomorphism of the encryption scheme. Thus, instead of relying on expensive generic non-interactive zero knowledge proofs for proving correct resharing, we utilize the algebraic structure and obtain extremely efficient proofs. Finally, we take a step back from communication in the YOSO model and ask a basic question of feasibility of perfect and fully secure protocols in the setting of standard MPC but with a specific layered interaction pattern. We answer this question in the affirmative and prove interesting implications for the YOSO model and other areas of dynamic MPC.