Welcome to the resource topic for 2024/251
Title:
Communication-Optimal Convex Agreement
Authors: Diana Ghinea, Chen-Da Liu-Zhang, Roger Wattenhofer
Abstract:Byzantine Agreement (BA) allows a set of n parties to agree on a value even when up to t of the parties involved are corrupted.
While previous works have shown that, for \ell-bit inputs, BA can be achieved with the optimal communication complexity \mathcal{O}(\ell n) for sufficiently large \ell, BA only ensures that honest parties agree on a meaningful output when they hold the same input, rendering the primitive inadequate for many real-world applications.
This gave rise to the notion of Convex Agreement (CA), introduced by Vaidya and Garg [PODC’13], which requires the honest parties’ outputs to be in the convex hull of the honest inputs. Unfortunately, all existing CA protocols incur a communication complexity of at least \Omega(\ell n^2).
In this work, we introduce the first CA protocol with the optimal communication of \mathcal{O}(\ell n) bits for inputs in \mathbb{Z} of size \ell = \Omega(\kappa \cdot n^2 \log n), where \kappa is the security parameter.
ePrint: https://eprint.iacr.org/2024/251
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 .