CryptoDB
Randomized Agreement, Verifiable Secret Sharing, and Multi Party Computation in Granular Synchrony
| Authors: |
|
|---|---|
| Download: | |
| Conference: | ASIACRYPT 2025 |
| Abstract: | Granular Synchrony (Giridharan et al. DISC 2024) is a new network model where the network is viewed as a graph consisting of synchronous, partially synchronous and asynchronous communication links. It has been shown that Granular Synchrony allows deterministic Byzantine agreement protocols to achieve a corruption threshold $n/3 \leq t < n/2$ in between complete asynchrony and complete synchrony if and only if the network satisfies the right condition, namely, if 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, being randomized, assume that all links are either synchronous or asynchronous, and do not assume any partially synchronous links. Our ACS protocol incurs an amortized communication cost of $O(n^3\lambda)$ bits per inputs, 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. |
BibTeX
@inproceedings{asiacrypt-2025-35914,
title={Randomized Agreement, Verifiable Secret Sharing, and Multi Party Computation in Granular Synchrony},
publisher={Springer-Verlag},
author={Ananya Appan and David Heath and Ling Ren},
year=2025
}