Paper 2026/1993
Network-Agnostic VSS with Quadratic Communication in Computational Setting
Abstract
Verifiable secret sharing (VSS) is a core primitive in multiparty computation (MPC). Bhimrajka et al. [PKC'24, TIT'26] proposed the first computationally network-agnostic VSS and VSS-based MPC, which seamlessly accommodate both synchronous and asynchronous network models. However, their VSS requires Byzantine Agreement (BA) and incurs $O(n^5)$ bits of communication per sharing among $n$ parties, and their MPC requires honest participation from nearly all parties. We revisit the network-agnostic VSS architecture and propose a more efficient and general network-agnostic VSS structure. Our key technique is a new virtual-party strategy, which introduces more parties for reconstruction. With this technique, network-agnostic VSS is BA-free and performs as efficiently as synchronous VSS. Specifically, in terms of communication, our VSS costs $O(n^2)$ bits in the one-shot case and $O(n)$ bits in the round-by-round case with the dispute-control technique, yielding the first computationally network-agnostic VSS protocols with amortized linear communication complexity. Besides, we further address a series of subtle yet necessary hurdles in adapting existing results to network-agnostic models, including the erasure coding techniques in Reliable Broadcast (RBC), packed secret sharing techniques in VSS, and the correlated polynomial techniques in MPC.
Note: Full version including appendices with detailed proofs and additional technical details.
Metadata
- Available format(s)
-
PDF
- Category
- Cryptographic protocols
- Publication info
- A major revision of an IACR publication in ASIACRYPT 2026
- Keywords
- Verifiable Secret SharingNetwork-AgnosticMultiparty ComputationCryptographic Security
- Contact author(s)
-
yusongyao @ whu edu cn
fengqi @ whu edu cn
cpeng @ whu edu cn
mluo @ whu edu cn
hedebiao @ whu edu cn - History
- 2026-09-14: approved
- 2026-09-12: received
- See all versions
- Short URL
- https://ia.cr/2026/1993
- License
-
CC BY-NC-ND
BibTeX
@misc{cryptoeprint:2026/1993,
author = {Yusong Yao and Qi Feng and Cong Peng and Min Luo and Debiao He},
title = {Network-Agnostic {VSS} with Quadratic Communication in Computational Setting},
howpublished = {Cryptology {ePrint} Archive, Paper 2026/1993},
year = {2026},
url = {https://eprint.iacr.org/2026/1993}
}
