Paper 2023/1813
Early Stopping for Any Number of Corruptions
Abstract
Minimizing the round complexity of byzantine broadcast is a fundamental question in distributed computing and cryptography. In this work, we present the first early stopping byzantine broadcast protocol that tolerates up to $t=n-1$ malicious corruptions and terminates in $O(\min\{f^2,t+1\})$ rounds for any execution with $f\leq t$ actual corruptions. Our protocol is deterministic, adaptively secure, and works assuming a plain public key infrastructure. Prior early-stopping protocols all either require honest majority or tolerate only up to $t=(1-\epsilon)n$ malicious corruptions while requiring either trusted setup or strong number theoretic hardness assumptions. As our key contribution, we show a novel tool called a polariser that allows us to transfer certificate-based strategies from the honest majority setting to settings with a dishonest majority.
Note: This revision contains a complete description of how to obtain polynomial complexity by compressing messages in the protocol.
Metadata
- Available format(s)
-
PDF
- Category
- Cryptographic protocols
- Publication info
- A major revision of an IACR publication in EUROCRYPT 2024
- Keywords
- Consensus
- Contact author(s)
-
lossjulian @ gmail com
jbn @ cs au dk - History
- 2024-09-20: last of 2 revisions
- 2023-11-23: received
- See all versions
- Short URL
- https://ia.cr/2023/1813
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2023/1813,
author = {Julian Loss and Jesper Buus Nielsen},
title = {Early Stopping for Any Number of Corruptions},
howpublished = {Cryptology {ePrint} Archive, Paper 2023/1813},
year = {2023},
url = {https://eprint.iacr.org/2023/1813}
}
