DROPS

Document

DOI: 10.4230/LIPIcs.ITCS.2025.1

Simple Is COOL: Graded Dispersal and Its Applications for Byzantine Fault Tolerance

Authors: Ittai Abraham, Gilad Asharov, and Anirudh Chandramouli

Published in: LIPIcs, Volume 325, 16th Innovations in Theoretical Computer Science Conference (ITCS 2025)

Abstract

The COOL protocol of Chen (DISC'21) is a major advance that enables perfect security for various tasks (in particular, Byzantine Agreement in Synchrony and Reliable Broadcast in Asynchrony). For an input of size L bits, its communication complexity is O(nL+n² log n), which is optimal up to a log n factor. Unfortunately, Chen’s analysis is rather intricate and complex. Our main contribution is a simple analysis of a new variant of COOL based on elementary counting arguments. Our main consistency proof takes less than two pages (instead of over 20 pages), making the COOL protocol much more accessible. In addition, the simple analysis allows us to improve the protocol by reducing one round of communication and reducing the communication complexity by 40%. In addition, we suggest a new way of extracting the core properties of COOL as a new primitive, which we call Graded Dispersal. We show how Graded Dispersal can then be used to obtain efficient solutions for Byzantine Agreement, Verifiable Information Dispersal, Gradecast, and Reliable Broadcast (in both Synchrony and Asynchrony, where appropriate). Our improvement of COOL directly applies here, and we improve the state-of-the-art in all those primitives by reducing at least one round and 40% communication.

Cite as

Ittai Abraham, Gilad Asharov, and Anirudh Chandramouli. Simple Is COOL: Graded Dispersal and Its Applications for Byzantine Fault Tolerance. In 16th Innovations in Theoretical Computer Science Conference (ITCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 325, pp. 1:1-1:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{abraham_et_al:LIPIcs.ITCS.2025.1,
  author =	{Abraham, Ittai and Asharov, Gilad and Chandramouli, Anirudh},
  title =	{{Simple Is COOL: Graded Dispersal and Its Applications for Byzantine Fault Tolerance}},
  booktitle =	{16th Innovations in Theoretical Computer Science Conference (ITCS 2025)},
  pages =	{1:1--1:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-361-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{325},
  editor =	{Meka, Raghu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.1},
  URN =		{urn:nbn:de:0030-drops-226295},
  doi =		{10.4230/LIPIcs.ITCS.2025.1},
  annote =	{Keywords: Byzantine Agreement, Broadcast}
}

Document

DOI: 10.4230/LIPIcs.DISC.2023.3

Network Agnostic Perfectly Secure MPC Against General Adversaries

Authors: Ananya Appan, Anirudh Chandramouli, and Ashish Choudhury

Published in: LIPIcs, Volume 281, 37th International Symposium on Distributed Computing (DISC 2023)

Abstract

In this work, we study perfectly-secure multi-party computation (MPC) against general (non-threshold) adversaries. Known protocols are secure against 𝒬^{(3)} and 𝒬^{(4)} adversary structures in a synchronous and an asynchronous network respectively. We address the existence of a single protocol which remains secure against 𝒬^{(3)} and 𝒬^{(4)} adversary structures in a synchronous and in an asynchronous network respectively, where the parties are unaware of the network type. We design the first such protocol against general adversaries. Our result generalizes the result of Appan, Chandramouli and Choudhury (PODC 2022), which presents such a protocol against threshold adversaries.

Cite as

Ananya Appan, Anirudh Chandramouli, and Ashish Choudhury. Network Agnostic Perfectly Secure MPC Against General Adversaries. In 37th International Symposium on Distributed Computing (DISC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 281, pp. 3:1-3:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{appan_et_al:LIPIcs.DISC.2023.3,
  author =	{Appan, Ananya and Chandramouli, Anirudh and Choudhury, Ashish},
  title =	{{Network Agnostic Perfectly Secure MPC Against General Adversaries}},
  booktitle =	{37th International Symposium on Distributed Computing (DISC 2023)},
  pages =	{3:1--3:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-301-0},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{281},
  editor =	{Oshman, Rotem},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2023.3},
  URN =		{urn:nbn:de:0030-drops-191294},
  doi =		{10.4230/LIPIcs.DISC.2023.3},
  annote =	{Keywords: Verifiable Secret Sharing, Byzantine Agreement, Perfect Security}
}

Search Results

Documents authored by Chandramouli, Anirudh

Simple Is COOL: Graded Dispersal and Its Applications for Byzantine Fault Tolerance

Abstract

Cite as

Network Agnostic Perfectly Secure MPC Against General Adversaries

Abstract

Cite as

Thanks for your feedback!

Could not send message