Paper 2018/829
Information-Theoretic Broadcast with Dishonest Majority for Long Messages
Wutichai Chongchitmate and Rafail Ostrovsky
Abstract
Byzantine broadcast is a fundamental primitive for secure computation. In a setting with $n$ parties in the presence of an adversary controlling at most $t$ parties, while a lot of progress in optimizing communication complexity has been made for $t < n/2$, little progress has been made for the general case $t<n$, especially for information-theoretic security. In particular, all information-theoretic secure broadcast protocols for $\ell$-bit messages and $t<n$ and optimal round complexity $\mathcal{O}(n)$ have, so far, required a communication complexity of $\mathcal{O}(\ell n^2)$. A broadcast extension protocol allows a long message to be broadcast more efficiently using a small number of single-bit broadcasts. Through broadcast extension, so far, the best achievable round complexity for $t<n$ setting with the optimal communication complexity of $\mathcal{O}(\ell n)$ is $\mathcal{O}(n^4)$ rounds. In this work, we construct a new broadcast extension protocol for $t<n$ with information-theoretic security. Our protocol improves the round complexity to $\mathcal{O}(n^3)$ while maintaining the optimal communication complexity for long messages. Our result shortens the gap between the information-theoretic setting and the computational setting, and between the optimal communication protocol and the optimal round protocol in the information-theoretic setting for $t<n$.
Metadata
- Available format(s)
- Category
- Cryptographic protocols
- Publication info
- Published by the IACR in TCC 2018
- Keywords
- Byzantine broadcastinformation-theoretic securitydishonest majorityround complexity
- Contact author(s)
- wutichai ch @ chula ac th
- History
- 2018-09-06: received
- Short URL
- https://ia.cr/2018/829
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2018/829, author = {Wutichai Chongchitmate and Rafail Ostrovsky}, title = {Information-Theoretic Broadcast with Dishonest Majority for Long Messages}, howpublished = {Cryptology {ePrint} Archive, Paper 2018/829}, year = {2018}, url = {https://eprint.iacr.org/2018/829} }