CryptoDB
Asymptotically Optimal Early Termination for Dishonest Majority Broadcast
| Authors: |
|
|---|---|
| Download: | |
| Conference: | EUROCRYPT 2025 |
| Abstract: | Deterministic broadcast protocols among $n$ parties tolerating $t$ corruptions require $\min\{f+2, t+1\}$ rounds, where $f \le t$ is the actual number of corruptions in an execution of the protocol. We provide the first protocol which is optimally resilient, adaptively secure, and asymptotically matches this lower bound for any $t<(1-\varepsilon)n$. By contrast, the best known algorithm in this regime by Loss and Nielsen (EUROCRYPT'24) always requires $O(\min\{f^2, t\})$ rounds. Our main technical tool is a generalization of the notion of polarizer introduced by Loss and Nielsen, which allows parties to obtain transferable cryptographic evidence of missing messages with less rounds of interaction. |
BibTeX
@inproceedings{eurocrypt-2025-35121,
title={Asymptotically Optimal Early Termination for Dishonest Majority Broadcast},
publisher={Springer-Verlag},
author={Giovanni Deligios and Ivana Klasovita and Chen-Da Liu-Zhang},
year=2025
}