Paper 2021/503

Almost-Asynchronous MPC under Honest Majority, Revisited

Matthieu Rambaud and Antoine Urban

Abstract

Multiparty computation does not tolerate $n/3$ corruptions under a plain asynchronous communication network, whatever the computational assumptions. However, Beerliová-Hirt-Nielsen [BHN, Podc'10] showed that, assuming access to a synchronous broadcast at the beginning of the protocol, enables to tolerate up to $t<n/2$ corruptions. This model is denoted as ``Almost asynchronous'' MPC. Yet, their work [BHN] has limitations: (i) \emph{Setup assumptions:} their protocol is based on an encryption scheme, with homomorphic additivity, which requires that a trusted entity gives to players secret shares of a global decryption key ahead of the protocol. It was left as an open question in [BHN] whether one can remove this assumption, denoted as ``trusted setup''. (ii) \emph{Common Randomness generation:} the generation of threshold additively homomorphic encrypted randomness uses the broadcast, therefore is allowed only at the beginning of the protocol (iii) \emph{Proactive security:} the previous limitation directly precludes the possibility of tolerating a mobile adversary. Indeed, tolerance to this kind of adversary, which is denoted as ``proactive'' MPC, would require, in the above setup, a mechanism by which players refresh their secret shares of the global key, which requires \emph{on-the-fly} generation of common randomness. (iv) \emph{Triple generation latency: } The protocol to preprocess the material necessary for multiplication has latency $t$, which is thus linear in the number of players. We remove all the previous limitations. Of independent interest, the novel computation framework that we introduce for proactivity, revolves around players denoted as ``kings'', which, in contrast to Podc'10, are now \emph{replaceable} after every elementary step of the computation.

Note: Change log w.r.t. Version 3 - 3 September 2021: Removed NIZK in the TAE and the non-proactive protocol of Thm 1, explicit succinct NIZK. Change log w.r.t. Version 4 - 8 November 2021: Univariate PVSS, UC Proofs, noninteractive proactive refresh, AAMPC from TFHE.