International Association
for Cryptologic Research

An important requirement in synchronous protocols is that, even when a party receives all its messages for a given round ahead of time, it must wait until the round officially concludes before sending its messages for the next round. In practice, however, implementations often overlook this waiting requirement. This leads to a mismatch between the security analysis and real-world deployments, giving adversaries a new, unaccounted-for capability: the ability to "peek into the future." Specifically, an adversary can force certain honest parties to advance to round $r+1$, observe their round $r+1$ messages, and then use this information to determine its remaining round $r$ messages. We refer to adversaries with this capability as "super-rushing" adversaries. We initiate a study of secure computation in the presence of super-rushing adversaries. We focus on understanding the conditions under which existing synchronous protocols remain secure in the presence of super-rushing adversaries. We show that not all protocols remain secure in this model, highlighting a critical gap between theoretical security guarantees and practical implementations. Even worse, we show that security against super-rushing adversaries is not necessarily maintained under sequential composition. Despite those limitations, we present a general positive result: secret-sharing based protocols in the perfect setting, such as BGW, or those that are based on multiplication triplets, remain secure against super-rushing adversaries. This general theorem effectively enhances the security of such protocols "for free." It shows that these protocols do not require parties to wait for the end of a round, enabling potential optimizations and faster executions without compromising security. Moreover, it shows that there is no need to spend efforts to achieve perfect synchronization when establishing the communication networks for such protocols.

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).