1 Search Results for "Loss, Julian"

Document

DOI: 10.4230/LIPIcs.DISC.2018.36

Strong Separations Between Broadcast and Authenticated Channels

Authors: Julian Loss, Ueli Maurer, and Daniel Tschudi

Published in: LIPIcs, Volume 121, 32nd International Symposium on Distributed Computing (DISC 2018)

Abstract

In the theory of distributed systems and cryptography one considers a setting with n parties, (often) connected via authenticated bilateral channels, who want to achieve a certain goal even if some fraction of the parties is dishonest. A classical goal of this type is to construct a broadcast channel. A broadcast channel guarantees that all honest recipients get the same value v (consistency) and, if the sender is honest, that v is the sender's input (validity). Lamport et al. showed that it is possible to construct broadcast if and only if the fraction of cheaters is less than a third. A natural question, first raised by Lamport, is whether there are weaker, still useful primitives achievable from authenticated channels. He proposed weak broadcast, where the validity condition must hold only if all parties are honest, and showed that it can be achieved with an unbounded number of protocol rounds, while broadcast cannot, suggesting that weak broadcast is in a certain sense weaker than broadcast. The purpose of this paper is to deepen the investigation of the separation between broadcast and authenticated channels. This is achieved by proving the following results. First, we prove a stronger impossibility result for 3-party broadcast. Even if two of the parties can broadcast, one can not achieve broadcast for the third party. Second, we prove a strong separation between authenticated channels and broadcast by exhibiting a new primitive, called XOR-cast, which satisfies two conditions: (1) XOR-cast is strongly unachievable (even with small error probability) from authenticated channels (which is not true for weak broadcast), and (2) broadcast is strongly unachievable from XOR-cast (and authenticated channels). This demonstrates that the hierarchy of primitives has a more complex structure than previously known. Third, we prove a strong separation between weak broadcast and broadcast which is not implied by Lamport's results. The proofs of these results requires the generalization of known techniques for impossibility proofs.

Cite as

Julian Loss, Ueli Maurer, and Daniel Tschudi. Strong Separations Between Broadcast and Authenticated Channels. In 32nd International Symposium on Distributed Computing (DISC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 121, pp. 36:1-36:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{loss_et_al:LIPIcs.DISC.2018.36,
  author =	{Loss, Julian and Maurer, Ueli and Tschudi, Daniel},
  title =	{{Strong Separations Between Broadcast and Authenticated Channels}},
  booktitle =	{32nd International Symposium on Distributed Computing (DISC 2018)},
  pages =	{36:1--36:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-092-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{121},
  editor =	{Schmid, Ulrich and Widder, Josef},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2018.36},
  URN =		{urn:nbn:de:0030-drops-98252},
  doi =		{10.4230/LIPIcs.DISC.2018.36},
  annote =	{Keywords: cryptography, multi-party computation, broadcast, impossibility}
}

Refine by Author
1 Loss, Julian
1 Maurer, Ueli
1 Tschudi, Daniel

Refine by Classification
1 Theory of computation → Cryptographic protocols

Refine by Keyword
1 broadcast
1 cryptography
1 impossibility
1 multi-party computation

Refine by Type
1 document

Refine by Publication Year
1 2018

1 Search Results for "Loss, Julian"

Strong Separations Between Broadcast and Authenticated Channels

Abstract

Cite as

Thanks for your feedback!

Could not send message