Information-Theoretic Broadcast with Dishonest Majority for Long Messages
Wutichai Chongchitmate, 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\).
comment:
TCC (1) 2018: 370-388
Fetch PDF file of the paper