Paper 2024/770

Sublinear-Round Broadcast without Trusted Setup

Andreea B. Alexandru, Duality Technologies
Julian Loss, Helmholtz Center for Information Security
Charalampos Papamanthou, Yale University
Giorgos Tsimos, University of Maryland, College Park
Benedikt Wagner, Helmholtz Center for Information Security
Abstract

Byzantine broadcast is one of the fundamental problems in distributed computing. Many of its practical applications, from multiparty computation to consensus mechanisms for blockchains, require increasingly weaker trust assumptions, as well as scalability for an ever-growing number of users $n$. This rules out existing solutions which run in a linear number of rounds in $n$ or rely on trusted setup requirements. In this paper, we propose the first sublinear-round and trustless Byzantine broadcast protocol for the dishonest majority setting. Unlike previous sublinear-round protocols, our protocol assumes neither the existence of a trusted dealer who honestly issues keys and correlated random strings to the parties nor random oracles. Instead, we present a solution whose setup is limited to an unstructured uniform reference string and a plain public key infrastructure (a.k.a. bulletin-board PKI). Our broadcast protocol builds on top of a moderated gradecast protocol which parties can use to reach weak agreement on shared random strings. Using these strings, we can then run in an unbiased fashion a committee-based Byzantine protocol, similar to that of Chan et al. (PKC 2020), which terminates in a sublinear number of rounds. To this end, we propose a novel construction for committee election, which does not rely either on random oracles or on a trusted setup, and uses NIZKs and time-lock puzzles. Our protocol is resilient against an adaptive adversary who corrupts any constant fraction of parties.

Note: This work is an extensive update, including additional authors, of a previous work which can be found in https://eprint.iacr.org/2022/1383

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint.
Keywords
Byzantine AgreementConsensus
Contact author(s)
aalexandru @ dualitytech com
loss @ cispa de
charalampos papamanthou @ yale edu
tsimos @ umd edu
benedikt wagner @ cispa de
History
2024-06-04: revised
2024-05-20: received
See all versions
Short URL
https://ia.cr/2024/770
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2024/770,
      author = {Andreea B. Alexandru and Julian Loss and Charalampos Papamanthou and Giorgos Tsimos and Benedikt Wagner},
      title = {Sublinear-Round Broadcast without Trusted Setup},
      howpublished = {Cryptology ePrint Archive, Paper 2024/770},
      year = {2024},
      note = {\url{https://eprint.iacr.org/2024/770}},
      url = {https://eprint.iacr.org/2024/770}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.