Paper 2025/1327

Randomized Agreement, Verifiable Secret Sharing and Multi-Party Computation in Granular Synchrony

Abstract

Granular Synchrony (Giridharan et al. DISC 2024) is a new network model that unifies the classic timing models of synchrony and asynchrony. The network is viewed as a graph consisting of a mixture of synchronous, eventually synchronous, and asynchronous communication links. It has been shown that Granular Synchrony allows deterministic Byzantine agreement protocols to achieve a corruption threshold in between complete synchrony and complete asynchrony if and only if the network graph satisfies the right condition, namely, that no two groups of honest parties of size $n-2t$ can be partitioned from each other. In this work, we show that the same network condition is also tight for Agreement on a Common Subset (ACS), Verifiable Secret Sharing (VSS), and secure Multi-Party Computation (MPC) with guaranteed output delivery, when the corruption threshold is between one-third and one-half. Our protocols are randomized and assume that all links are either synchronous or asynchronous. %(no partially synchronous links are needed). Our ACS protocol incurs an amortized communication cost of $O(n^3\lambda)$ bits per input, and our VSS and MPC protocols incur amortized communication costs of $O(n^3)$ and $O(n^4)$ field elements per secret and per multiplication gate, respectively. To design our protocols, we also construct protocols for Reliable Broadcast and Externally Valid Byzantine Agreement (EVBA), which are of independent interest.