International Association
for Cryptologic Research

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, [BHN] suffers from limitations: (i) {Setup assumptions:} their protocol is based on an encryption scheme, with homomorphic additivity, such that the secret keys of players are given by a trusted entity ahead of the protocol. It was left as an open question in [BHN] whether one can remove this assumption, denoted as ``trusted setup''. (ii) {Common Randomness generation:} the generation of common random secrets uses the broadcast, therefore is allowed only at the beginning of the protocol. (iii) {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 a mechanism by which players refresh their (shares of) keys, without the intervention of a trusted entity, with {on the fly} randomness generation. (iv) {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, our novel computation framework revolves around players, denoted as ``kings'', which, in contrast to Podc'10, are now \emph{replaceable} after every elementary step of the computation.