Paper 2025/2006
OmniBA: Round-Efficient BA with Quadratic Communication under Mixed Faults
Abstract
We present a simple and efficient Byzantine Agreement protocol in the mixed fault model where up to $t$ parties can be Byzantine, up to $s$ parties can be send-omission, and up to $r$ parties can be receive-omission such that $2t+s+r<n$. Our synchronous protocol greatly improves over the efficiency of the state-of-the-art solution due to Loss and Stern [TCC '23]. Specifically, our protocol incurs an expected communication complexity of $O(n^2)$ instead of $O(n^5)$ in their construction, while maintaining the same resilience. Our protocol terminates in an expected constant number of rounds, provided that a constant fraction of parties are non-faulty.
Metadata
- Available format(s)
-
PDF
- Category
- Cryptographic protocols
- Publication info
- Preprint.
- Keywords
- Byzantine AgreementOmission FaultsRound Efficiency
- Contact author(s)
-
simonhkamp @ gmail com
lossjulian @ gmail com
kartik1507 @ gmail com
kcshi97 @ gmail com - History
- 2025-10-30: approved
- 2025-10-27: received
- See all versions
- Short URL
- https://ia.cr/2025/2006
- License
-
CC0
BibTeX
@misc{cryptoeprint:2025/2006,
author = {Simon Holmgaard Kamp and Julian Loss and Kartik Nayak and Kecheng Shi},
title = {{OmniBA}: Round-Efficient {BA} with Quadratic Communication under Mixed Faults},
howpublished = {Cryptology {ePrint} Archive, Paper 2025/2006},
year = {2025},
url = {https://eprint.iacr.org/2025/2006}
}
