CryptoDB
Paper: Information-Theoretic Broadcast with Dishonest Majority for Long Messages
| Authors: | |
|---|---|
| Download: | |
| Conference: | TCC 2018 |
| 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$$t<n/2, little progress has been made for the general case $$t<n$$t<n, especially for information-theoretic security. In particular, all information-theoretic secure broadcast protocols for $$\ell $$ℓ-bit messages and $$t<n$$t<n and optimal round complexity $${\mathcal {O}}(n)$$O(n) have, so far, required a communication complexity of $${\mathcal {O}}(\ell n^2)$$O(ℓn2). 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$$t<n setting with the optimal communication complexity of $${\mathcal {O}}(\ell n)$$O(ℓn) is $${\mathcal {O}}(n^4)$$O(n4) rounds.In this work, we construct a new broadcast extension protocol for $$t<n$$t<n with information-theoretic security. Our protocol improves the round complexity to $${\mathcal {O}}(n^3)$$O(n3) 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$$t<n. |
BibTeX
@inproceedings{tcc-2018-28991,
title={Information-Theoretic Broadcast with Dishonest Majority for Long Messages},
booktitle={Theory of Cryptography},
series={Theory of Cryptography},
publisher={Springer},
volume={11239},
pages={370-388},
doi={10.1007/978-3-030-03807-6_14},
author={Wutichai Chongchitmate and Rafail Ostrovsky},
year=2018
}