Byzantine agreement and byzantine broadcast are the two most fundamental problems and essential building blocks in secure multiparty computations, and improving their efficiency is of interest to both theorists and practitioners. In this survey, we describe the most important constructions of Byzantine agreement and Byzantine broadcast, as well as their extension protocols.
Download file
Counter downloads: 2
- Title Byzantine agreement and byzantine broadcast
- Headline Byzantine agreement and byzantine broadcast
- Publesher
Tomsk State University - Issue Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics 71
- Date:
- DOI 10.17223/20710410/71/3
Keywords
Byzantine agreement, Byzantine broadcast, cryptographic protocolAuthors
References
Рацеев С. М. Криптография. Безопасные многосторонние вычисления: учеб, пособие для вузов. 2-е изд., испр. и доп. СПб.: Лайв, 2025. 540 с.
Berman Р., Garay J. A., and Perry К. J. Bit-optimal distributed consensus // R. Baeza-Yates and U. Manber (eds.).Computer Science. Boston, MA: Springer, 1992. P.313-322.
Lamport L., Shostak R., and Pease M. The Byzantine generals problem // ACM Trans. Program. Lang. Svst. 1982. V.4. No.3. P.382-401.
Pfitzmann B. and Waidner M. Information-Theoretic Pseudosignatures and Byzantine Agreement for t < n/3. Technical Report RZ 2882. IBM Research, 1996.
Kumaresan R. Broadcast and Verifiable Secret Sharing: New Security Models and Round Optimal Constructions. PhD Thesis. University of Maryland at College Park, 2012.
Dolev D. and Strong H. R. Authenticated algorithms for Byzantine agreement // SIAM J.Computing. 1983. V. 12. No. 4. P. 656-666.
Cleve R. Limits on the security of coin flips when half the processors are faulty // Proc. STOC’86. Berkeley, California, USA, 1986. P.364-369.
Goldwasser S. and Lindell Y. Secure computation without agreement // J. Cryptology. 2005. V. 18. No. 3. P. 247-287.
Dolev D. and Reischuk R. Bounds on information exchange for Byzantine agreement // Proc. PODS’82. Ottawa, Canada, 1982. P. 132-140.
Ganesh C. and Patra A. Optimal extension protocols for Byzantine broadcast and agreement // Distrib.Comput. 2021. V.34. P.59-77.
Ben-Or M., Canetti R., and Goldreich O. Asynchronous secure computation // Proc. STOC’93. N.Y., USA, 1993. P.52-61.
Рацеев С. M. Элементы высшей алгебры и теории кодирования: учеб, пособие для вузов. 2-е изд., испр. и доп. СПб.: Лайв, 2023. 684с.
Fitzi М. and Flirt М. Optimally efficient multi-valued Byzantine agreement // Proc. PODC’06. Denver, Colorado, USA, 2006. P. 163-168.
Hirt M. and Raykov P. Multi-valued Byzantine broadcast: the t < n case // LNCS. 2014. V. 8874. P. 448-465.
Nayak K., Ren L., Shi E., et al. Improved Extension Protocols for Byzantine Broadcast and Agreement. arXiv:2002.11321. https://arxiv.org/abs/2002.11321. 2020.
Byzantine agreement and byzantine broadcast | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2026. № 71. DOI: 10.17223/20710410/71/3
Download full-text version
Counter downloads: 45