Search Results

Documents authored by Maurer, Ueli

Document
DOI: 10.4230/LIPIcs.OPODIS.2020.25
On Broadcast in Generalized Network and Adversarial Models

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

Published in: LIPIcs, Volume 184, 24th International Conference on Principles of Distributed Systems (OPODIS 2020)

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.
Cite as

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)

Copy BibTex To Clipboard

@InProceedings{liuzhang_et_al:LIPIcs.OPODIS.2020.25,
  author =	{Liu-Zhang, Chen-Da and Maram, Varun and Maurer, Ueli},
  title =	{{On Broadcast in Generalized Network and Adversarial Models}},
  booktitle =	{24th International Conference on Principles of Distributed Systems (OPODIS 2020)},
  pages =	{25:1--25:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-176-4},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{184},
  editor =	{Bramas, Quentin and Oshman, Rotem and Romano, Paolo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2020.25},
  URN =		{urn:nbn:de:0030-drops-135108},
  doi =		{10.4230/LIPIcs.OPODIS.2020.25},
  annote =	{Keywords: broadcast, partial broadcast, minicast, general adversary, general network}
}
Document
Brief Announcement
DOI: 10.4230/LIPIcs.DISC.2019.47
Brief Announcement: Towards Byzantine Broadcast in Generalized Communication and Adversarial Models

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

Published in: LIPIcs, Volume 146, 33rd International Symposium on Distributed Computing (DISC 2019)

Abstract
Byzantine 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 - w.r.t. 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 such that broadcast is achievable from a complete set of b-minicasts is shown. 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]. Our contributions include: 1) proposing a hierarchy over all possible general adversaries for a clean analysis of the broadcast problem in general networks, 2) showing the infeasibility of a prominent technique - used to achieve broadcast in general 3-minicast networks [Ravikant et al., 2004] - with regard to higher b-minicast networks, and 3) providing some necessary conditions on general networks for broadcast to be possible while tolerating general adversaries.
Cite as

Chen-Da Liu-Zhang, Varun Maram, and Ueli Maurer. Brief Announcement: Towards Byzantine Broadcast in Generalized Communication and Adversarial Models. In 33rd International Symposium on Distributed Computing (DISC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 146, pp. 47:1-47:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{liuzhang_et_al:LIPIcs.DISC.2019.47,
  author =	{Liu-Zhang, Chen-Da and Maram, Varun and Maurer, Ueli},
  title =	{{Brief Announcement: Towards Byzantine Broadcast in Generalized Communication and Adversarial Models}},
  booktitle =	{33rd International Symposium on Distributed Computing (DISC 2019)},
  pages =	{47:1--47:3},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-126-9},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{146},
  editor =	{Suomela, Jukka},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2019.47},
  URN =		{urn:nbn:de:0030-drops-113540},
  doi =		{10.4230/LIPIcs.DISC.2019.47},
  annote =	{Keywords: broadcast, partial broadcast, minicast, general adversary, general network}
}
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.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}
}
Document
DOI: 10.4230/DagRep.1.9.76
Public-Key Cryptography (Dagstuhl Seminar 11391)

Authors: Marc Fischlin, Anna Lysyanskaya, Ueli Maurer, and Alexander May

Published in: Dagstuhl Reports, Volume 1, Issue 9 (2012)

Abstract
From September 25th till September 30th, 2011, the Dagstuhl Seminar 11391 about ``Public-Key Cryptography'' took place at Schloss Dagstuhl. The meeting hosted 33 international researchers and incited active discussions about recent developments in this area.
Cite as

Marc Fischlin, Anna Lysyanskaya, Ueli Maurer, and Alexander May. Public-Key Cryptography (Dagstuhl Seminar 11391). In Dagstuhl Reports, Volume 1, Issue 9, pp. 76-94, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@Article{fischlin_et_al:DagRep.1.9.76,
  author =	{Fischlin, Marc and Lysyanskaya, Anna and Maurer, Ueli and May, Alexander},
  title =	{{Public-Key Cryptography (Dagstuhl Seminar 11391)}},
  pages =	{76--94},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2012},
  volume =	{1},
  number =	{9},
  editor =	{Fischlin, Marc and Lysyanskaya, Anna and Maurer, Ueli and May, Alexander},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.1.9.76},
  URN =		{urn:nbn:de:0030-drops-33685},
  doi =		{10.4230/DagRep.1.9.76},
  annote =	{Keywords: Fully-Homomorphic Encryption, Leakage-Resilience, Constructive Cryptography}
}
Document
DOI: 10.4230/DagSemProc.07381.1
07381 Abstracts Collection – Cryptography

Authors: Johannes Blömer, Dan Boneh, Ronald Cramer, and Ueli Maurer

Published in: Dagstuhl Seminar Proceedings, Volume 7381, Cryptography (2008)

Abstract
From 16.09.2007 to 21.09.2007 the Dagstuhl Seminar 07381 ``Cryptography'' was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.
Cite as

Johannes Blömer, Dan Boneh, Ronald Cramer, and Ueli Maurer. 07381 Abstracts Collection – Cryptography. In Cryptography. Dagstuhl Seminar Proceedings, Volume 7381, pp. 1-19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{blomer_et_al:DagSemProc.07381.1,
  author =	{Bl\"{o}mer, Johannes and Boneh, Dan and Cramer, Ronald and Maurer, Ueli},
  title =	{{07381 Abstracts Collection – Cryptography}},
  booktitle =	{Cryptography},
  pages =	{1--19},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{7381},
  editor =	{Johannes Bl\"{o}mer and Dan Boneh and Ronald Cramer and Ueli Maurer},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.07381.1},
  URN =		{urn:nbn:de:0030-drops-12935},
  doi =		{10.4230/DagSemProc.07381.1},
  annote =	{Keywords: Cryptography, information security, public-key cryptography, cryptographic protocols, security proofs}
}
Document
DOI: 10.4230/DagSemProc.07381.2
07381 Executive Summary - Cryptography

Authors: Johannes Blömer, Dan Boneh, Ronald Cramer, and Ueli Maurer

Published in: Dagstuhl Seminar Proceedings, Volume 7381, Cryptography (2008)

Abstract
The topics covered in the seminar spanned most areas of cryptography, in one way or another, both in terms of the types of schemes (public-key cryptography, symmetric cryptography, hash functions and other cryptographic functions, multi-party protocols, etc.) and in terms of the mathematical methods and techniques used (algebra, number theory, elliptic curves, probability theory, information theory, combinatorics, quantum theory, etc.). The range of applications addressed in the various talks was broad, ranging from secure communication, key management, authentication, digital signatures and payment systems to e-voting and Internet security. While the initial plan had been to focus more exclusively on public-key cryptography, it turned out that this sub-topic branches out into many other areas of cryptography and therefore the organizers decided to expand the scope, emphasizing quality rather than close adherence to public-key cryptography. This decision turned out to be a wise one. What was common to almost all the talks is that rigorous mathematical proofs for the security of the presented schemes were given. In fact, a central topic of many of the talks were proof methodologies for various contexts.
Cite as

Johannes Blömer, Dan Boneh, Ronald Cramer, and Ueli Maurer. 07381 Executive Summary - Cryptography. In Cryptography. Dagstuhl Seminar Proceedings, Volume 7381, pp. 1-2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{blomer_et_al:DagSemProc.07381.2,
  author =	{Bl\"{o}mer, Johannes and Boneh, Dan and Cramer, Ronald and Maurer, Ueli},
  title =	{{07381 Executive Summary - Cryptography}},
  booktitle =	{Cryptography},
  pages =	{1--2},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{7381},
  editor =	{Johannes Bl\"{o}mer and Dan Boneh and Ronald Cramer and Ueli Maurer},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.07381.2},
  URN =		{urn:nbn:de:0030-drops-12928},
  doi =		{10.4230/DagSemProc.07381.2},
  annote =	{Keywords: Cryptography, information security, public-key cryptography, cryptographic protocols, security proofs}
}
Document
DOI: 10.4230/DagSemRep.355
Cryptography (Dagstuhl Seminar 02391)

Authors: Ueli Maurer, Adi Shamir, Jacques Stern, and Moti Yung

Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)

Abstract
Cite as

Ueli Maurer, Adi Shamir, Jacques Stern, and Moti Yung. Cryptography (Dagstuhl Seminar 02391). Dagstuhl Seminar Report 355, pp. 1-21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2003)

Copy BibTex To Clipboard

@TechReport{maurer_et_al:DagSemRep.355,
  author =	{Maurer, Ueli and Shamir, Adi and Stern, Jacques and Yung, Moti},
  title =	{{Cryptography (Dagstuhl Seminar 02391)}},
  pages =	{1--21},
  ISSN =	{1619-0203},
  year =	{2003},
  type = 	{Dagstuhl Seminar Report},
  number =	{355},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemRep.355},
  URN =		{urn:nbn:de:0030-drops-152357},
  doi =		{10.4230/DagSemRep.355},
}
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
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact