Paper 2013/745

Asynchronous MPC with a Strict Honest Majority Using Non-equivocation

Michael Backes, Fabian Bendun, Ashish Choudhury, and Aniket Kate


Multiparty computation (MPC) among n parties can tolerate up to t<n/2 active corruptions in a synchronous communication setting; however, in an asynchronous communication setting, the resiliency bound decreases to only t<n/3 active corruptions. We improve the resiliency bound for asynchronous MPC (AMPC) to match synchronous MPC using non-equivocation. Non-equivocation is a message authentication mechanism to restrict a corrupted sender from making conflicting statements to different (honest) parties. It can be implemented using an increment-only counter and a digital signature oracle, realizable with trusted hardware modules readily available in commodity computers and smartphone devices. A non-equivocation mechanism can also be transferable and allow a receiver to verifiably transfer the authenticated statement to other parties. In this work, using transferable non-equivocation, we present an AMPC protocol tolerating t<n/2 faults. From a practical point of view, our AMPC protocol requires fewer setup assumptions than the previous AMPC protocol with t<n/2 by Beerliovä-Trub\'ıniovä, Hirt and Nielsen [PODC 2010]: unlike their AMPC protocol, it does not require any synchronous broadcast round at the beginning of the protocol and avoids the threshold homomorphic encryption setup assumption. Moreover, our AMPC protocol is also efficient and provides a gain of \Theta(n) in the communication complexity per multiplication gate, over the AMPC protocol of Beerliovä-Trub\'ıniovä et al. In the process, using non-equivocation, we also define the first asynchronous verifiable secret sharing (AVSS) scheme with t<n/2, which is of independent interest to threshold cryptography.

Note: Non-equivocation definition and protocols pseudocodes are refined.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. Major revision. ACM PODC 2014
Multiparty Computation (MPC)Asynchronous Communication SettingResiliencyNon-equivocationVerifiable Secret SharingReduced Assumptions
Contact author(s)
aniket @ mmci uni-saarland de
partho31 @ gmail com
2014-06-17: last of 5 revisions
2013-11-17: received
See all versions
Short URL
Creative Commons Attribution


      author = {Michael Backes and Fabian Bendun and Ashish Choudhury and Aniket Kate},
      title = {Asynchronous {MPC} with a Strict Honest Majority Using Non-equivocation},
      howpublished = {Cryptology ePrint Archive, Paper 2013/745},
      year = {2013},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.