Paper 2022/378

Share $\&$ Shrink: (In-)Feasibility of MPC from one Broadcast-then-Asynchrony, and Delegated Computation

Abstract

We consider protocols for secure multi-party computation (MPC) under honest majority, i.e., for $n$=$2t+1$ players of which $t$ are corrupt, that achieve guaranteed output delivery (GOD), and operate in a single initial round of broadcast (BC), followed by steps of asynchronous peer-to-peer (P2P) messages. The power of closely related ``hybrid networks'' was studied in [Fitzi-Nielsen, Disc'09], [BHN, Podc'10] and [Patra-Ravi, IEEE Tr. Inf. Theory'18]. The interest of such protocols is that they go at the actual speed of the network, and security is preserved under arbitrary network conditions (past the initial BC). We first complete the picture of this model with an impossibility result showing that some setup is required to achieve honest majority MPC with GOD. We then consider a bare bulletin-board PKI setup, and leverage recent advances in multi-key homomorphic encryption [BJMS, Asiacrypt'20], to state the feasibility of MPC in a tight 1-BC-then-1 single step of asynchronous P2P messages. We then consider efficiency. The only protocols adaptable to such a network model and setup are [BJMS, Asiacrypt'20], which does not scale well for many players, and [GLS, Crypto'15], which does not support input delegation from external resource-constrained owners (such as IoT devices or smartphones), limiting its practical use. Our main contribution is a generic design that enables MPC in 1BC-then-asynchronous P2P. It operates over ciphertexts encrypted under a (threshold) single-key encryption scheme, resulting in the smallest sizes expectable and efficient evaluation. It can be implemented from any homomorphic encryption scheme built from linear maps (e.g., GSW, CL, ...). Our main building block is the squishing of the verifiable input sharing (``Share''), in parallel with the distributed key generation (DKG) in the single BC, followed by threshold encryption (``Shrink'') in one asynchronous step. Interestingly, it can be compiled as the first constant-round YOSO protocol in 1 BC.

Note: Change log w.r.t. Version 2 of 2023-06-09: (a) Simplified presentation, with details about the linear BFV scheme imported from eprint 2024/1285; (b) Experimental evaluation.