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 .