Cryptology ePrint Archive: Report 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 \cite[Podc'10]{podc10} 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, \cite{podc10} suffers from 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 \cite{podc10} 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 (iii), revolves around players denoted as ``kings'', which, in contrast to Podc'10, are now \emph{replaceable} after every elementary step of the computation.

Category / Keywords: cryptographic protocols /

Date: received 18 Apr 2021, last revised 12 May 2021

Contact author: matthieu rambaud at telecom-paris fr, antoine urban@telecom-paris fr

Available format(s): PDF | BibTeX Citation

Note: Change log w.r.t. Version 1 - 18 April 2021: Minor clarifications in the Introduction and Model Change log w.r.t. Version 2 - 19 April 2021: Clarifications, in particular in the new triples generation and the proactive protocol.

Version: 20210512:113047 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]