Paper 2026/182

Computing in a Safe House: Accountable Universally Composable Asynchronous Secure Distributed Computing

Abstract

In non-synchronous networks, partitioning arguments show that $t$-resilient protocols among $n$ processes can typically not guarantee safety when the number of malicious processes $f$ is $\geq n - 2t$. This fragility motivates augmenting such protocols with accountability schemes to deter safety violations. So far however, such schemes have been limited in their verifiability, scalability or privacy. This paper presents $\tau_{zk\text{-}scr}$, a universal compiler that circumvents such limitations. The compiler transforms any protocol $\mathcal{P}$, that is secure against semi-honest crash-failure adversaries, into a Byzantine-tolerant, accountable counterpart $\bar{\mathcal{P}}$. Essentially, we devise $\tau_{zk\text{-}scr}$ by deconstructing the celebrated CLOS compiler (STOC 2002), observing that each resulting component is ``easily accountable'', and globally propagating the accountability through the reconstruction. The guarantees provided by $\tau_{zk\text{-}scr}$ are defined with respect to a resilience threshold $t_{\epsilon} = \lceil n (\frac{1}{3}-\epsilon) \rceil - 1$, for any $\epsilon \geq 0$. $\bar{\mathcal{P}}$ preserves the hyperproperties of $\mathcal{P}$, including privacy, input-independence, correctness, and output delivery, whenever $f \leq t_{\epsilon}$. If $f > t_{\epsilon}$, then either: (1) $\bar{\mathcal{P}}$ emulates $\mathcal{P}$, in the sense that all its hypersafety properties are preserved, though output delivery may not occur; or (2) all correct processes obtain externally verifiable proofs of misbehavior involving a significant subset of faulty parties. By adjusting its parameters, $\tau_{zk\text{-}scr}$ achieves various trade-offs. Assuming a transparent setup, for any strictly positive constant $\epsilon \in \Omega(1)$, the most efficient instantiation provides security against a 1-delayed-adaptive adversary (i.e., where corruption decisions are postponed just long enough to allow messages in transit to be delivered) with $o(n^2)$ multiplicative communication overhead. Our results are formalized and proven following the Accountable Universal Composability (AUC) blueprint (S&P 2023), an extension of UC designed to support modular analysis of accountability guarantees.