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 $$ parties in the presence of an adversary controlling at most $$ parties, while a lot of progress in optimizing communication complexity has been made for $$, little progress has been made for the general case $$, especially for information-theoretic security. In particular, all information-theoretic secure broadcast protocols for $$-bit messages and $$ and optimal round complexity $$ have, so far, required a communication complexity of $$. 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 $$ setting with the optimal communication complexity of $$ is $$ rounds. In this work, we construct a new broadcast extension protocol for $$ with information-theoretic security. Our protocol improves the round complexity to $$ 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 $$.