Paper 2020/894
Nearly Quadratic Broadcast Without Trusted Setup Under Dishonest Majority
Georgios Tsimos and Julian Loss and Charalampos Papamanthou
Abstract
Broadcast (BC) is a crucial ingredient for many protocols in distributed computing and cryptography. In this paper we study its communication complexity against an adversary that controls a majority of the parties. In this setting, all known protocols either exhibit a communication complexity of more than $O(n^3)$ bits (where $n$ is the number of parties) or crucially rely on a trusted party to generate cryptographic keys before the execution of the protocol. We give the first protocol for BC that achieves $\tilde O(n^2 \cdot \kappa)$ bits of communication (where $\kappa$ is the security parameter) under a dishonest majority and minimal cryptographic setup assumptions, i.e., where no trusted setup is required and parties just need to generate their own cryptographic keys. Our protocol is randomized and combines the classic Dolev-Strong protocol with network gossiping techniques to minimize communication. Our analysis of the main random process employs Chernoff bounds for negatively-associated variables and might be of independent interest.
Metadata
- Available format(s)
- Category
- Cryptographic protocols
- Publication info
- Preprint. MINOR revision.
- Keywords
- broadcast
- Contact author(s)
- tsimos @ umd edu,jloss @ umiacs umd edu,cpap @ umd edu
- History
- 2022-06-24: last of 3 revisions
- 2020-07-16: received
- See all versions
- Short URL
- https://ia.cr/2020/894
- License
-
CC BY