[Resource Topic] 2021/503: Almost-Asynchronous MPC under Honest Majority, Revisited

Welcome to the resource topic for 2021/503

Almost-Asynchronous MPC under Honest Majority, Revisited

Authors: Matthieu Rambaud, Antoine Urban


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.

ePrint: https://eprint.iacr.org/2021/503

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .