### Almost-Surely Terminating Asynchronous Byzantine Agreement Against General Adversaries with Optimal Resilience

##### Abstract

In this work, we present an almost-surely terminating asynchronous Byzantine agreement (ABA) protocol for $n$ parties. Our protocol requires ${\cal O}(n^2)$ expected time and is secure against a computationally-unbounded malicious (Byzantine) adversary, characterized by a non-threshold adversary structure ${\cal Z}$, which enumerates all possible subsets of potentially corrupt parties. Our protocol has optimal resilience where ${\cal Z}$ satisfies the ${\cal Q}^{(3)}$ condition; i.e. union of no three subsets from ${\cal Z}$ covers all the $n$ parties. To the best of our knowledge, this is the first almost-surely terminating ABA protocol with ${\cal Q}^{(3)}$ condition. Previously, almost-surely terminating ABA protocol is known with non-optimal resilience where ${\cal Z}$ satisfies the ${\cal Q}^{(4)}$ condition; i.e. union of no four subsets from ${\cal Z}$ covers all the $n$ parties. To design our protocol, we present a shunning asynchronous verifiable secret-sharing (SAVSS) scheme with ${\cal Q}^{(3)}$ condition, which is of independent interest.

Available format(s)
Category
Cryptographic protocols
Publication info
Preprint.
Keywords
Byzantine agreement asynchronous network general adversary verifiable secret sharing almost-surely termination
Contact author(s)
ashish choudhury @ iiitb ac in
History
2022-07-24: last of 4 revisions
See all versions
Short URL
https://ia.cr/2022/917

CC0

BibTeX

@misc{cryptoeprint:2022/917,
author = {Ashish Choudhury},
title = {Almost-Surely Terminating Asynchronous Byzantine Agreement Against General Adversaries with Optimal Resilience},
howpublished = {Cryptology ePrint Archive, Paper 2022/917},
year = {2022},
note = {\url{https://eprint.iacr.org/2022/917}},
url = {https://eprint.iacr.org/2022/917}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.