Welcome to the resource topic for 2022/1383
Title:
Sublinear-round Broadcast without trusted setup against dishonest majority
Authors: Andreea B. Alexandru, Julian Loss, Charalampos Papamanthou, Giorgos Tsimos
Abstract:Byzantine broadcast is a central component of several cryptographic protocols, from secure multiparty computation to consensus mechanisms for blockchains. Many practical applications require increasingly weaker trust assumptions, as well as scalability for an ever-growing number of users, which rules out existing solutions with linear number of rounds or trusted setup requirements. This poses the question of achieving broadcast with efficient communication and round complexity against powerful adversarial models and without trusted setup assumptions.
In this paper, we answer this question positively. We present a Broadcast protocol that runs in rounds sublinear in n, the number of users, with asymptotic communication \tilde O(n^3). Our protocol does not assume the existence of a trusted dealer who issues keys or common random strings. Instead, it is built upon a trustless verifiable delay function and the existence of random oracles in order to achieve a graded form of shared randomness between parties. This graded shared randomness acts as an untrusted online setup that can be used to securely run a committee-based protocol, similar to Chan et al. (PKC 2020). We also show that the graded shared randomness protocol we design can be used to seed multiple instances of Broadcast, which further amortizes the communication cost per instance to \tilde O(n^2) over n instances or even to \tilde O(n) per n instances of parallel Broadcast.
ePrint: https://eprint.iacr.org/2022/1383
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .