Welcome to the resource topic for 2018/829
Title:
Information-Theoretic Broadcast with Dishonest Majority for Long Messages
Authors: 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.
ePrint: https://eprint.iacr.org/2018/829
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .