International Association
for Cryptologic Research

We study broadcast protocols in the information-theoretic model under optimal conditions, where the number of corruptions $t$ is at most one-third of the parties, $n$. While worst-case $\Omega(n)$ round broadcast protocols are known to be impossible to achieve, protocols with an expected constant number of rounds have been demonstrated since the seminal work of Feldman and Micali [STOC'88]. Communication complexity for such protocols has gradually improved over the years, reaching $O(nL)$ plus expected $O(n^4\log n)$ for broadcasting a message of size $L$ bits. This paper presents a perfectly secure broadcast protocol with expected constant rounds and communication complexity of $O(nL)$ plus expected $O(n^3 \log^2n)$ bits. In addition, we consider the problem of parallel broadcast, where $n$ senders, each wish to broadcast a message of size $L$. We show a parallel broadcast protocol with expected constant rounds and communication complexity of $O(n^2L)$ plus expected $O(n^3 \log^2n)$ bits. Our protocol is optimal (up to expectation) for messages of length $L \in \Omega(n \log^2 n)$. Our main contribution is a framework for obtaining \emph{perfectly} secure broadcast with an expected constant number of rounds from a \emph{statistically} secure verifiable secret sharing. Moreover, we provide a new statistically secure verifiable secret sharing where the broadcast cost per participant is reduced from $O(n \log n)$ bits to only $O(\poly \log n)$ bits. All our protocols are adaptively secure.

In this paper, we design unconditionally secure multi-party computation (MPC) protocols in the asynchronous communication setting with optimal resilience. Our protocols are secure against a computationally unbounded malicious adversary characterized by an adversary structure $$\mathcal {Z}$$ Z , which enumerates all possible subsets of potentially corrupt parties. We present protocols with both perfect-security , as well as with statistical-security . While the protocols in the former class achieve all the security properties in an error-free fashion, the protocols belonging to the latter category achieve all the security properties except with a negligible error. Our perfectly secure protocol incurs an amortized communication of $$\mathcal {O}(|\mathcal {Z}|^2)$$ O ( | Z | 2 ) bits per multiplication. This improves upon the protocol of Choudhury and Pappu (INDOCRYPT 2020) with the least known amortized communication complexity of $$\mathcal {O}(|\mathcal {Z}|^3)$$ O ( | Z | 3 ) bits per multiplication. On the other hand, our statistically secure protocol incurs an amortized communication of $$\mathcal {O}(|\mathcal {Z}|)$$ O ( | Z | ) bits per multiplication. This is the first statistically secure asynchronous MPC protocol against general adversaries. Previously, perfectly secure and statistically secure MPC with an amortized communication cost of $$\mathcal {O}(|\mathcal {Z}|^2)$$ O ( | Z | 2 ) and $$\mathcal {O}(|\mathcal {Z}|)$$ O ( | Z | ) bits, respectively, per multiplication was known only in the relatively simpler synchronous communication setting (Hirt and Tschudi in ASIACRYPT, Springer, 2013).