On Broadcast in Generalized Network and Adversarial Models

Authors Chen-Da Liu-Zhang, Varun Maram, Ueli Maurer



PDF
Thumbnail PDF

File

LIPIcs.OPODIS.2020.25.pdf
  • Filesize: 0.77 MB
  • 16 pages

Document Identifiers

Author Details

Chen-Da Liu-Zhang
  • Department of Computer Science, ETH Zürich, Switzerland
Varun Maram
  • Department of Computer Science, ETH Zürich, Switzerland
Ueli Maurer
  • Department of Computer Science, ETH Zürich, Switzerland

Cite AsGet BibTex

Chen-Da Liu-Zhang, Varun Maram, and Ueli Maurer. On Broadcast in Generalized Network and Adversarial Models. In 24th International Conference on Principles of Distributed Systems (OPODIS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 184, pp. 25:1-25:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.OPODIS.2020.25

Abstract

Broadcast is a primitive which allows a specific party to distribute a message consistently among n parties, even if up to t parties exhibit malicious behaviour. In the classical model with a complete network of bilateral authenticated channels, the seminal result of Pease et al. [Pease et al., 1980] shows that broadcast is achievable if and only if t < n/3. There are two generalizations suggested for the broadcast problem - with respect to the adversarial model and the communication model. Fitzi and Maurer [Fitzi and Maurer, 1998] consider a (non-threshold) general adversary that is characterized by the subsets of parties that could be corrupted, and show that broadcast can be realized from bilateral channels if and only if the union of no three possible corrupted sets equals the entire set of n parties. On the other hand, Considine et al. [Considine et al., 2005] extend the standard model of bilateral channels with the existence of b-minicast channels that allow to locally broadcast among any subset of b parties; the authors show that in this enhanced model of communication, secure broadcast tolerating up to t corrupted parties is possible if and only if t < (b-1)/(b+1)n. These generalizations are unified in the work by Raykov [Raykov P., 2015], where a tight condition on the possible corrupted sets is presented such that broadcast is achievable from a complete set of b-minicasts. This paper investigates the achievability of broadcast in general networks, i.e., networks where only some subsets of minicast channels may be available, thereby addressing open problems posed in [Jaffe et al., 2012; Raykov P., 2015]. To that end, we propose a hierarchy over all possible general adversaries, and identify for each class of general adversaries 1) a set of minicast channels that are necessary to achieve broadcast and 2) a set of minicast channels that are sufficient to achieve broadcast. In particular, this allows us to derive bounds on the amount of b-minicasts that are necessary and that suffice towards constructing broadcast in general b-minicast networks.

Subject Classification

ACM Subject Classification
  • Theory of computation → Cryptographic protocols
  • Theory of computation → Distributed algorithms
  • Security and privacy → Cryptography
Keywords
  • broadcast
  • partial broadcast
  • minicast
  • general adversary
  • general network

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. P. Berman, J. A. Garay, and K. J. Perry. Bit optimal distributed consensus. In Computer Science Research, pages 313-322, New York, NY, USA, 1992. Plenum Publishing Corporation. Google Scholar
  2. B. A. Coan and J. L. Welch. Modular construction of a byzantine agreement protocol with optimal message bit complexity. Information and Computation, 97:61-85, March 1992. Google Scholar
  3. J. Considine, M. Fitzi, M. Franklin, L. A. Levin, U. Maurer, and D. Metcalf. Byzantine agreement given partial broadcast. Journal of Cryptology, 18(3):191-217, July 2005. Google Scholar
  4. M. Fitzi and U. Maurer. From partial consistency to global broadcast. In F. Yao, editor, Proc. 32nd ACM Symposium on Theory of Computing - STOC 2000, pages 494-503. ACM, May 2000. Google Scholar
  5. M. Fitzi and U. M. Maurer. Efficient byzantine agreement secure against general adversaries. In S. Kutten, editor, DISC, volume 1499 of Lecture Notes in Computer Science, pages 134-148. Springer, 1998. Google Scholar
  6. O. Goldreich, S. Micali, and A. Wigderson. How to play any mental game. In Proceedings of the 19th annual ACM symposium on theory of computing, STOC '87, pages 218-229, New York, NY, USA, 1987. ACM. Google Scholar
  7. Martin Hirt and Ueli Maurer. Complete characterization of adversaries tolerable in secure multi-party computation. In PODC, volume 97, pages 25-34, 1997. Google Scholar
  8. A. Jaffe, T. Moscibroda, and S. Sen. On the price of equivocation in byzantine agreement. In D. Kowalski and A. Panconesi, editors, ACM Symposium on Principles of Distributed Computing, PODC '12, Funchal, Madeira, Portugal, July 16-18, 2012, pages 309-318. ACM, 2012. Google Scholar
  9. Raykov P. Broadcast from minicast secure against general adversaries. In M. M. Halldórsson, K. Iwama, N. Kobayashi, and B. Speckmann, editors, ICALP 2015: 42nd International Colloquium on Automata, Languages and Programming, Part II, Kyoto, Japan, July 6-10, 2015, volume 9135 of Lecture Notes in Computer Science, pages 701-712. Springer, Berlin, Germany, 2015. Google Scholar
  10. M. C. Pease, R. E. Shostak, and L. Lamport. Reaching agreement in the presence of faults. Journal of the ACM, 27(2):228-234, 1980. Google Scholar
  11. D. V. S. Ravikant, M. Venkitasubramaniam, V. Srikanth, K. Srinathan, and C. P. Rangan. On byzantine agreement over (2,3)-uniform hypergraphs. In R. Guerraoui, editor, Distributed Computing, 18th International Conference, DISC 2004, Amsterdam, The Netherlands, October 4-7, 2004, Proceedings, volume 3274 of Lecture Notes in Computer Science, pages 450-464. Springer, 2004. Google Scholar
  12. A. C. Yao. Protocols for secure computations. In Proceedings of the 23rd Annual Symposium on Foundations of Computer Science, SFCS '82, pages 160-164, Washington, DC, USA, 1982. IEEE Computer Society. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail