Welcome to the resource topic for 2022/711
Title:
Efficient and Adaptively Secure Asynchronous Binary Agreement via Binding Crusader Agreement
Authors: Ittai Abraham, Naama Ben-David, and Sravya Yandamuri
Abstract:We present a new abstraction based on crusader agreement called \textit{Binding Crusader Agreement} (BCA) for solving binary consensus in the \textit{asynchronous} setting against an \textit{adaptive} adversary. BCA has the validity, agreement, and termination properties of crusader agreement in addition to a new property called \textit{binding}. Binding states that before the first non-faulty party terminates, there is a value v \in \{0,1\} such that no non-faulty party can output the value v in any continuation of the execution. We believe that reasoning about binding explicitly, as a first order goal, greatly helps algorithm design, clarity, and analysis. Using our framework, we solve several versions of asynchronous binary agreement against an adaptive adversary in a simple and modular manner that either improves or matches the efficiency of state of the art solutions. We do this via new BCA protocols, given a strong common coin, and via new Graded BCA protocols given an \epsilon-good common coin. For crash failures, we reduce the expected time to terminate and we provide termination bounds that are linear in the goodness of the common coin. For Byzantine failures, we improve the expected time to terminate in the computational setting with threshold signatures, and match the state of the art in the information theoretic setting, both with a strong common coin and with an \epsilon-good common coin.
ePrint: https://eprint.iacr.org/2022/711
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .