Welcome to the resource topic for 2025/246
Title:
Towards Optimal Early Stopping Agreement Protocols
Authors: Fatima Elsheimy, Julian Loss, Charalampos Papamanthou
Abstract:Early stopping agreement protocols guarantee termination based on the actual number of malicious parties, f \leq t, encountered during execution, rather than assuming the worst-case scenario of t2. In this scenario, the best known protocol due to Elsheimy, Loss, and Papamanthou (ASIACRYPT `24) achieves a round complexity of (1+\epsilon)\cdot f for some constant 0<\epsilon<1. We begin by introducing an improvement to the Elsheimy et al. approach which can be used to obtain the first polynomial-time early stopping agreement protocols in the t2 corruption regime which achieve a complexity of f+O(\sqrt{f}). We then instantiate our generic framework with refined components to obtain a very concretely efficient protocol with a round complexity of only f + 6\lceil\sqrt{f}\rceil+6 and polynomial communication complexity. Finally, we show that it is possible to come within one round of the optimal round complexity by presenting a broadcast protocol based on the exponential information gathering approach, which achieves a round complexity of \min\{f + 3, t + 1\}, albeit with exponential communication complexity.
ePrint: https://eprint.iacr.org/2025/246
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 .