Search Results

Documents authored by Asharov, Gilad

Document
DOI: 10.4230/LIPIcs.DISC.2025.1
ABEL: Perfect Asynchronous Byzantine Extension from List-Decoding

Authors: Ittai Abraham and Gilad Asharov

Published in: LIPIcs, Volume 356, 39th International Symposium on Distributed Computing (DISC 2025)

Abstract
Asynchronous byzantine agreement extension studies the message complexity of L-bit multivalued asynchronous byzantine agreement given access to a binary asynchronous Byzantine agreement protocol. We prove that asynchronous byzantine agreement extension can be solved with perfect security and optimal resilience in O(nL+n² log n) total communication (in bits) in addition to a single call to a binary asynchronous Byzantine agreement protocol. For L = O(n log n), this gives an asymptotically optimal protocol, resolving a question that remained open for nearly two decades. List decoding is a fundamental concept in theoretical computer science and cryptography, enabling error correction beyond the unique decoding radius and playing a critical role in constructing robust codes, hardness amplification, and secure cryptographic protocols. A key novelty of our perfectly secure and optimally resilient asynchronous byzantine agreement extension protocol is that it uses list decoding - making a striking new connection between list decoding and asynchronous Byzantine agreement.
Cite as

Ittai Abraham and Gilad Asharov. ABEL: Perfect Asynchronous Byzantine Extension from List-Decoding. In 39th International Symposium on Distributed Computing (DISC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 356, pp. 1:1-1:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{abraham_et_al:LIPIcs.DISC.2025.1,
  author =	{Abraham, Ittai and Asharov, Gilad},
  title =	{{ABEL: Perfect Asynchronous Byzantine Extension from List-Decoding}},
  booktitle =	{39th International Symposium on Distributed Computing (DISC 2025)},
  pages =	{1:1--1:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-402-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{356},
  editor =	{Kowalski, Dariusz R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2025.1},
  URN =		{urn:nbn:de:0030-drops-248185},
  doi =		{10.4230/LIPIcs.DISC.2025.1},
  annote =	{Keywords: Asynchronous Byzantine Agreement, Perfect Security}
}
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.ITC.2022.15
Static vs. Adaptive Security in Perfect MPC: A Separation and the Adaptive Security of BGW

Authors: Gilad Asharov, Ran Cohen, and Oren Shochat

Published in: LIPIcs, Volume 230, 3rd Conference on Information-Theoretic Cryptography (ITC 2022)

Abstract
Adaptive security is a highly desirable property in the design of secure protocols. It tolerates adversaries that corrupt parties as the protocol proceeds, as opposed to static security where the adversary corrupts the parties at the onset of the execution. The well-accepted folklore is that static and adaptive securities are equivalent for perfectly secure protocols. Indeed, this folklore is backed up with a transformation by Canetti et al. (EUROCRYPT'01), showing that any perfectly secure protocol that is statically secure and satisfies some basic requirements is also adaptively secure. Yet, the transformation results in an adaptively secure protocol with inefficient simulation (i.e., where the simulator might run in super-polynomial time even if the adversary runs just in polynomial time). Inefficient simulation is problematic when using the protocol as a sub-routine in the computational setting. Our main question is whether an alternative efficient transformation from static to adaptive security exists. We show an inherent difficulty in achieving this goal generically. In contrast to the folklore, we present a protocol that is perfectly secure with efficient static simulation (therefore also adaptively secure with inefficient simulation), but for which efficient adaptive simulation does not exist (assuming the existence of one-way permutations). In addition, we prove that the seminal protocol of Ben-Or, Goldwasser and Wigderson (STOC'88) is secure against adaptive, semi-honest corruptions with efficient simulation. Previously, adaptive security of the protocol, as is, was only known either for a restricted class of circuits, or for all circuits but with inefficient simulation.
Cite as

Gilad Asharov, Ran Cohen, and Oren Shochat. Static vs. Adaptive Security in Perfect MPC: A Separation and the Adaptive Security of BGW. In 3rd Conference on Information-Theoretic Cryptography (ITC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 230, pp. 15:1-15:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{asharov_et_al:LIPIcs.ITC.2022.15,
  author =	{Asharov, Gilad and Cohen, Ran and Shochat, Oren},
  title =	{{Static vs. Adaptive Security in Perfect MPC: A Separation and the Adaptive Security of BGW}},
  booktitle =	{3rd Conference on Information-Theoretic Cryptography (ITC 2022)},
  pages =	{15:1--15:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-238-9},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{230},
  editor =	{Dachman-Soled, Dana},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2022.15},
  URN =		{urn:nbn:de:0030-drops-164933},
  doi =		{10.4230/LIPIcs.ITC.2022.15},
  annote =	{Keywords: secure multiparty computation, perfect security, adaptive security, BGW protocol}
}
Document
DOI: 10.4230/LIPIcs.ITC.2020.11
Oblivious Parallel Tight Compaction

Authors: Gilad Asharov, Ilan Komargodski, Wei-Kai Lin, Enoch Peserico, and Elaine Shi

Published in: LIPIcs, Volume 163, 1st Conference on Information-Theoretic Cryptography (ITC 2020)

Abstract
In tight compaction one is given an array of balls some of which are marked 0 and the rest are marked 1. The output of the procedure is an array that contains all of the original balls except that now the 0-balls appear before the 1-balls. In other words, tight compaction is equivalent to sorting the array according to 1-bit keys (not necessarily maintaining order within same-key balls). Tight compaction is not only an important algorithmic task by itself, but its oblivious version has also played a key role in recent constructions of oblivious RAM compilers. We present an oblivious deterministic algorithm for tight compaction such that for input arrays of n balls requires O(n) total work and O(log n) depth. Our algorithm is in the Exclusive-Read-Exclusive-Write Parallel-RAM model (i.e., EREW PRAM, the most restrictive PRAM model), and importantly we achieve asymptotical optimality in both total work and depth. To the best of our knowledge no earlier work, even when allowing randomization, can achieve optimality in both total work and depth.
Cite as

Gilad Asharov, Ilan Komargodski, Wei-Kai Lin, Enoch Peserico, and Elaine Shi. Oblivious Parallel Tight Compaction. In 1st Conference on Information-Theoretic Cryptography (ITC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 163, pp. 11:1-11:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{asharov_et_al:LIPIcs.ITC.2020.11,
  author =	{Asharov, Gilad and Komargodski, Ilan and Lin, Wei-Kai and Peserico, Enoch and Shi, Elaine},
  title =	{{Oblivious Parallel Tight Compaction}},
  booktitle =	{1st Conference on Information-Theoretic Cryptography (ITC 2020)},
  pages =	{11:1--11:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-151-1},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{163},
  editor =	{Tauman Kalai, Yael and Smith, Adam D. and Wichs, Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2020.11},
  URN =		{urn:nbn:de:0030-drops-121164},
  doi =		{10.4230/LIPIcs.ITC.2020.11},
  annote =	{Keywords: Oblivious tight compaction, parallel oblivious RAM, EREW PRAM}
}
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact