On the Complexity of Broadcast Setup
Martin Hirt and Pavel Raykov
Byzantine broadcast is a distributed primitive that allows a specific party (called “sender”) to consistently distribute a value $v$ among $n$ parties in the presence of potential misbehavior of up to $t$ of the parties. Broadcast requires that correct parties always agree on the same value and if the sender is correct, then the agreed value is $v$. Broadcast without a setup (i.e., from scratch) is achievable from point-to-point channels if and only if $t < n/3$. In case $t \ge n/3$ a trusted setup is required. The setup may be assumed to be given initially or generated by the parties in a setup phase.
It is known that generating setup for protocols with cryptographic security is relatively simple and only consists of setting up a public-key infrastructure. However, generating setup for information-theoretically secure protocols is much more involved. In this paper we study the complexity of setup generation for information-theoretic protocols using point-to-point channels and temporarily available broadcast channels. We optimize the number of rounds in which the temporary broadcast channels are used while minimizing the number of bits broadcast with them. We give the first information-theoretically secure broadcast protocol tolerating $t < n/2$ that uses the temporary broadcast channels during only 1 round in the setup phase. Furthermore, only $\mathcal{O}(n^3)$ bits need to be broadcast with the temporary broadcast channels during that round, independently of the security parameter employed. The broadcast protocol presented in this paper allows to construct the first information-theoretically secure MPC protocol which uses a broadcast channel during only one round. Additionally, the presented broadcast protocol supports refreshing, which allows to broadcast an a priori unknown number of times given a fixed-size setup.
BibTeX Citation
@inproceedings{HirRay13a,
author = {Martin Hirt and Pavel Raykov},
title = {On the Complexity of Broadcast Setup},
editor = {Fedor V. Fomin and Rusins Freivalds and Marta Z. Kwiatkowska and David Peleg},
booktitle = {Automata, Languages, and Programming --- 40th International Colloquium, ICALP (1)},
pages = {552--563},
series = {Lecture Notes in Computer Science},
volume = {7965},
year = {2013},
month = {7},
publisher = {Springer},
}