Paper 2022/378

Share \& Shrink: (In-)Feasibility of MPC from one Broadcast-then-Asynchrony, and Improved Complexity

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 which operate in $1$ single initial round of broadcast (BC), followed by some steps of asynchronous peer-to-peer (P2P) messages. The power of closely related ``hybrid networks'' was studied in [Fitzi-Nielsen, Disc'09], [Beerliova-Hirt-Nielsen, Podc'10], [Patra-Ravi, IEEE Trans. Inf. Theory'18] and [Choudhury, Podc'20]. Interest of such protocols is that they go at the actual speed of the network, and their security is preserved under arbitrary network conditions (past the initial broadcast). 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 on multi-key fully homomorphic encryption [BJMS, Asiacrypt'20], to state feasibility of MPC in a tight 1 BC then 1 single step of asynchronous P2P. We then consider efficiency. The only protocols which can be adapted to tolerate such network model and setup are [Gordon-Liu-Shi, Crypto'15] and [BJMS, Asiacrypt'20]. The former does not allow inputs from external lightweight owners and is inherently limited to the GSW FHE, while the sizes of the ciphertexts of the latter are quadratic in the number of input owners. Our main contribution is a very simple and generic design which enables MPC in 1BC-then-asynchronous P2P. It operates over ciphertexts encrypted over a (threshold) single-key encryption scheme. Hence, they have the smallest sizes expectable. It operates from any public key encryption scheme with a key generation, encryption and decryption which are built from linear maps (such as GSW, BFV, CL). Our main building block is the squishing in the BC of both the publicly verifiable sharing of the inputs (``Share''), in parallel with distributed key generation (DKG), then followed by threshold encryption (``Shrink'') in one step of asynchronous P2P. As a bonus, this design allows inputs from possibly lightweight external owners. We then aim at instantiating the design from the BFV FHE, but surprisingly there exists no robust threshold BFV scheme. Precisely, all existing protocols for generating a common relinearisation key can abort as soon as one player deviates. We solve this issue, with a relinearisation key (adapted from [CDKS, CCS'19]) which we show how to securely generate in parallel of the threshold key, in the same broadcast. We thus obtain the first robust threshold BFV. We believe that this contribution is of independent interest. Of independent interest, as an optional alternative, we propose the first threshold FHE decryption enabling simultaneously: (i) robustness under asynchrony with honest majority; (ii) tolerating a power-of-small-prime ciphertext modulus, e.g., $2^e$; and (iii) secret shares of sizes quasi-independent of $N$.

Note: Framework enlarged to various linearly homomorphic encryption schemes (GSW, CL) in addition to BFV. The Theorem 1 (feasibility of MPC in 1BC + 1 async P2P) has been imported from the Section 4.4.1 of eprint 2021/503 (8 November 2021 version).