CryptoDB
Early Stopping for Any Number of Corruptions
| Authors: |
|
|---|---|
| Download: |
|
| Presentation: | Slides |
| Conference: | EUROCRYPT 2024 |
| Abstract: | Minimizing the round complexity of byzantine broadcast is a fundamental question in distributed computing and cryptography. In this work, we present the first \emph{early stopping} byzantine broadcast protocol that tolerates up to $t=n-1$ malicious corruptions and terminates in $\cO(\min\{f^2,t+1\})$ rounds for any execution with $f\leq t$ \emph{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 \emph{polarizer} that allows us to transfer certificate-based strategies from the honest majority setting to settings with a dishonest majority. |
BibTeX
@inproceedings{eurocrypt-2024-33875,
title={Early Stopping for Any Number of Corruptions},
publisher={Springer-Verlag},
doi={10.1007/978-3-031-58734-4_16},
author={Julian Loss and Jesper Buus Nielsen},
year=2024
}