Paper 2008/424

Asynchronous Byzantine Agreement with Optimal Resilience

Arpita Patra, Ashish Choudhury, and C. Pandu Rangan

Abstract

We present an efficient, optimally-resilient Asynchronous Byzantine Agreement (ABA) protocol involving n = 3t+1 parties over a completely asynchronous network, tolerating a computationally unbounded Byzantine adversary, capable of corrupting at most t out of the n parties. In comparison with the best known optimally-resilient ABA protocols of Canetti and Rabin (STOC 1993) and Abraham, Dolev and Halpern (PODC 2008), our protocol is significantly more efficient in terms of the communication complexity. Our ABA protocol is built on a new statistical asynchronous verifiable secret sharing (AVSS) protocol with optimal resilience. Our AVSS protocol significantly improves the communication complexity of the only known statistical and optimally-resilient AVSS protocol of Canetti et al. Our AVSS protocol is further built on an asynchronous primitive called asynchronous weak commitment (AWC), while the AVSS of Canetti et al. is built on the primitive called asynchronous weak secret sharing (AWSS). We observe that AWC has weaker requirements than AWSS and hence it can be designed more efficiently than AWSS. The common coin primitive is one of the most important building blocks for the construction of an ABA protocol. In this paper, we extend the existing common coin protocol to make it compatible with our new AVSS protocol that shares multiple secrets simultaneously. As a byproduct, our new common coin protocol is more communication efficient than all the existing common coin protocols.

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. Major revision. PODC 2009 and PODC 2012
Keywords
Byzantine agreementComputationally unboundedSecret sharingCommon coin.
Contact author(s)
arpitapatra_10 @ yahoo co in
History
2013-10-11: last of 12 revisions
2008-10-02: received
See all versions
Short URL
https://ia.cr/2008/424
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2008/424,
      author = {Arpita Patra and Ashish Choudhury and C.  Pandu Rangan},
      title = {Asynchronous  Byzantine Agreement with Optimal Resilience},
      howpublished = {Cryptology ePrint Archive, Paper 2008/424},
      year = {2008},
      note = {\url{https://eprint.iacr.org/2008/424}},
      url = {https://eprint.iacr.org/2008/424}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.