You are looking at a specific version 20101224:105656 of this paper. See the latest version.

Paper 2008/424

Efficient Asynchronous Byzantine Agreement with Optimal Resilience

Arpita Patra and Ashish Choudhury and C. Pandu Rangan

Abstract

We present an efficient and optimally resilient Asynchronous Byzantine Agreement (ABA) protocol involving $n = 3t+1$ parties over a completely asynchronous network, tolerating a computationally unbounded Byzantine adversary, who can control at most $t$ parties. The amortized communication complexity of our ABA protocol is O(n^4 \log \frac{1}{\epsilon}) bits for attaining agreement on a single bit, where \epsilon (\epsilon > 0 denotes the probability of non-termination. We compare our protocol with most recent optimally resilient ABA protocols of [CR93] and [ADH08] and show that our protocol gains by a factor of O(n^7 (\log \frac{1}{\epsilon})^{3}) over the ABA of [CR93] and by a factor of O(n^4 \frac{\log{n}}{\log \frac{1}{\epsilon}}) over the ABA of [ADH08]. To design our protocol, we first present a novel, simple and optimally resilient statistical asynchronous verifiable secret sharing (AVSS) protocol with $n = 3t+1$, which significantly improves the communication complexity of the only known optimally resilient statistical AVSS protocol of [CR93]. Our AVSS shares multiple secrets concurrently and is far better than multiple parallel executions of AVSS sharing single secret. We believe that our AVSS can be used in many other applications for improving communication complexity and hence is of independent interest. The common coin primitive is one of the most important building blocks for the construction of ABA protocol. The only known efficient common coin protocol [FM97] uses multiple executions of AVSS sharing a single secret as a black-box. Unfortunately, this common coin protocol does not achieve its goal when multiple invocations of AVSS sharing single secret are replaced by single invocation of AVSS sharing multiple secrets. Therefore in this paper, we extend the existing common coin protocol to make it compatible with our new AVSS. As a byproduct, our new common coin protocol is much more communication efficient than the existing common coin protocol.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Published elsewhere. Unknown where it was published
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
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.