$\widetilde{\text{ O }}$ptimal Adaptively Secure Hash-Based MVBA and Asynchronous Common Subset

Asynchronous multiparty computation (AMPC) requires an input agreement phase where all participants have a consistent view of the set of private inputs. While the input agreement problem can be precisely addressed by a Byzantine fault-tolerant consensus known as Asynchronous Common Subset (ACS), existing ACS constructions with potential post-quantum security have a large $\widetilde{\mathcal{O}}(n^3)$ communication complexity for a network of $n$ nodes. This poses a bottleneck for AMPC in the same setting. In contrast, ACS has optimal constructions with quadratic communication complexity based on bilinear map assumptions.

In this paper, we bridge this gap by introducing a nearly optimal ACS, which, assuming a common coin oracle, relies on the blackbox use of collision-resistant hash functions. It exhibits $\widetilde{\mathcal{O}}(n^2)$ communication complexity, expected constant round complexity, and security against adaptive adversaries who can corrupt up to $n/3$ nodes and perform “after-the-fact-removal” attacks.

At the core of our new ACS is the first nearly optimal hash-based asynchronous Multi-valued Validated Byzantine Agreement (MVBA). To reduce cubic communication while avoiding heavy cryptographic tools, we introduce a new design paradigm with several novel components. This paradigm also enables an information-theoretic MVBA construction, whose communication complexity is higher than its hash-based counterpart but still quadratic. We give standard treatment of those using the conventional property based definitions. We also define and analyze our MVBA and components within the UC-framework, facilitating their modular use in broader applications, particularly in AMPC.