Information-Theoretic Broadcast with Dishonest Majority for Long Messages
Information-Theoretic Broadcast with Dishonest Majority for Long Messages
复制标题
长消息的不诚实多数的信息论广播
DOI：
--
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
R. Ostrovsky
中科院分区：
文献类型：
--
作者：
Wutichai Chongchitmate;R. Ostrovsky
拜占庭广播是安全计算的一个基本原语。在一个有n个参与方的环境中，当一个对手控制最多t个参与方时，虽然在优化通信复杂度方面已经取得了很大的进展（t < n/2），但在一般情况下（t<n），特别是在信息理论安全方面，进展甚微。特别地，到目前为止，用于（ell）比特消息和（t<n）以及最优轮复杂度（{mathcal {O}}（n））的所有信息论安全广播协议都需要（{mathcal {O}}（ell n^2））的通信复杂度。广播扩展协议允许使用少量的单比特广播来更有效地广播长消息。通过广播扩展，到目前为止，对于具有（{mathcal {0}}（ell n））的最佳通信复杂度的（t<n）设置，最佳可实现的轮复杂度是（{mathcal {0}}（n^4））轮。
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.