Show simple item record

dc.contributor.author
Liu Zhang, Chen-Da
dc.contributor.author
Maram, Varun
dc.contributor.author
Maurer, Ueli
dc.contributor.editor
Bramas, Quentin
dc.contributor.editor
Oshman, Rotem
dc.contributor.editor
Romano, Paolo
dc.date.accessioned
2021-08-11T09:26:36Z
dc.date.available
2020-11-16T10:22:17Z
dc.date.available
2020-11-16T11:36:30Z
dc.date.available
2021-03-15T10:45:11Z
dc.date.available
2021-08-11T09:25:16Z
dc.date.available
2021-08-11T09:26:36Z
dc.date.issued
2020-12
dc.identifier.isbn
978-3-95977-176-4
en_US
dc.identifier.issn
1868-8969
dc.identifier.other
10.4230/LIPIcs.OPODIS.2020.25
en_US
dc.identifier.uri
http://hdl.handle.net/20.500.11850/451523
dc.identifier.doi
10.3929/ethz-b-000451523
dc.description.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.
en_US
dc.format
application/pdf
en_US
dc.language.iso
en
en_US
dc.publisher
Schloss Dagstuhl - Leibniz-Zentrum für Informatik
en_US
dc.rights.uri
http://creativecommons.org/licenses/by/3.0/
dc.subject
broadcast
en_US
dc.subject
partial broadcast
en_US
dc.subject
minicast
en_US
dc.subject
general adversary
en_US
dc.subject
general network
en_US
dc.title
On Broadcast in Generalized Network and Adversarial Models
en_US
dc.type
Conference Paper
dc.rights.license
Creative Commons Attribution 3.0 Unported
dc.date.published
2021-01-25
ethz.journal.title
Leibniz International Proceedings in Informatics
ethz.journal.volume
184
en_US
ethz.journal.abbreviated
Leibniz int. proc. inform.
ethz.pages.start
25
en_US
ethz.size
21 p. accepted version
en_US
ethz.version.deposit
publishedVersion
en_US
ethz.event
24th Conference on Principles of Distributed Systems (OPODIS 2020) (virtual)
en_US
ethz.event.location
Strasbourg, France
en_US
ethz.event.date
December 14-16, 2020
en_US
ethz.notes
Conference lecture held on December 14, 2020. Due to the Coronavirus (COVID-19) the conference was conducted virtually.
en_US
ethz.publication.place
Dagstuhl
en_US
ethz.publication.status
published
en_US
ethz.leitzahl
ETH Zürich::00002 - ETH Zürich::00012 - Lehre und Forschung::00007 - Departemente::02150 - Dep. Informatik / Dep. of Computer Science::02660 - Institut für Informationssicherheit / Institute of Information Security::09653 - Paterson, Kenneth / Paterson, Kenneth
en_US
ethz.leitzahl
ETH Zürich::00002 - ETH Zürich::00012 - Lehre und Forschung::00007 - Departemente::02150 - Dep. Informatik / Dep. of Computer Science::02643 - Institut für Theoretische Informatik / Inst. Theoretical Computer Science::03338 - Maurer, Ueli / Maurer, Ueli
en_US
ethz.leitzahl.certified
ETH Zürich::00002 - ETH Zürich::00012 - Lehre und Forschung::00007 - Departemente::02150 - Dep. Informatik / Dep. of Computer Science::02660 - Institut für Informationssicherheit / Institute of Information Security::09653 - Paterson, Kenneth / Paterson, Kenneth
en_US
ethz.leitzahl.certified
ETH Zürich::00002 - ETH Zürich::00012 - Lehre und Forschung::00007 - Departemente::02150 - Dep. Informatik / Dep. of Computer Science::02643 - Institut für Theoretische Informatik / Inst. Theoretical Computer Science::03338 - Maurer, Ueli / Maurer, Ueli
ethz.relation.isPartOf
https://youtu.be/KhSunZDN7oE
ethz.date.deposited
2020-11-16T10:22:26Z
ethz.source
FORM
ethz.eth
yes
en_US
ethz.availability
Open access
en_US
ethz.rosetta.installDate
2021-03-15T10:45:24Z
ethz.rosetta.lastUpdated
2021-03-15T10:45:24Z
ethz.rosetta.exportRequired
true
ethz.rosetta.versionExported
true
ethz.COinS
ctx_ver=Z39.88-2004&amp;rft_val_fmt=info:ofi/fmt:kev:mtx:journal&amp;rft.atitle=On%20Broadcast%20in%20Generalized%20Network%20and%20Adversarial%20Models&amp;rft.jtitle=Leibniz%20International%20Proceedings%20in%20Informatics&amp;rft.date=2020-12&amp;rft.volume=184&amp;rft.spage=25&amp;rft.issn=1868-8969&amp;rft.au=Liu%20Zhang,%20Chen-Da&amp;Maram,%20Varun&amp;Maurer,%20Ueli&amp;rft.isbn=978-3-95977-176-4&amp;rft.genre=proceeding&amp;rft_id=info:doi/10.4230/LIPIcs.OPODIS.2020.25&amp;
 Search print copy at ETH Library

Files in this item

Thumbnail
Thumbnail

Publication type

Show simple item record