Share&Shrink: Efficient and Delegatable MPC in One Broadcast then Asynchrony

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 consider a bare bulletin-board PKI setup, and leverage recent advances in multi-key homomorphic encryption [BJMS, Asiacrypt’20], to state the feasibility of honest majority MPC with GOD 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 into the first constant-round YOSO protocol in 1 BC.