Linear-Communication ACSS with Guaranteed Termination and Lower Amortized Bound

Paper 2026/304

Linear-Communication ACSS with Guaranteed Termination and Lower Amortized Bound

Chengyi Qin, School of Mathematics, Shandong University, State Key Laboratory of Cryptography and Digital Economy Security, Jinan 250100, China, Singapore Management University

Mingqiang Wang, School of Mathematics, Shandong University, State Key Laboratory of Cryptography and Digital Economy Security, Jinan 250100, China

Haiyang Xue, Singapore Management University

Abstract

An Asynchronous Complete Secret Sharing (ACSS) protocol enables a dealer to distribute \( N \) Shamir shares such that all parties eventually receive their shares over an asynchronous network. It serves as a fundamental building block for asynchronous Secure Multiparty Computation (MPC) and Byzantine Agreement. In this work, we focus on the statistically secure ACSS with optimal resilience (\(t < n/3\)). Recently, Ji, Li, and Song~[CRYPTO'24] proposed the first ACSS protocol with amortized linear communication. However, their scheme lacks guaranteed termination, and they identified the construction of a linear-communication ACSS with guaranteed termination as an open problem. Furthermore, their protocol requires a large amortized bound of \( N = \Omega(n^{11} \kappa) \), where \( n \) is the number of parties and \( \kappa \) is the size of the secret. In this work, we resolve the open problem and significantly reduce the amortized bound by presenting a linear-communication ACSS protocol with guaranteed termination and a lower bound of \( N = \Omega(n^{4}+n\kappa) \). Our ACSS protocol can be directly applied to asynchronous MPC protocols, ensuring both guaranteed termination and improved communication per multiplication gate, as well as to asynchronous Byzantine Agreement.

Metadata

Available format(s): PDF
Publication info: A major revision of an IACR publication in EUROCRYPT 2026
Keywords: ACSS Guaranteed Termination Linear Communication Asynchronous Communication Model
Contact author(s): qcy521111 @ 163 com
wangmingqiang @ sdu edu cn
haiyangxue @ smu edu sg
History: 2026-02-18: approved; 2026-02-18: received; See all versions
Short URL: https://ia.cr/2026/304
License: CC BY

BibTeX

@misc{cryptoeprint:2026/304,
      author = {Chengyi Qin and Mingqiang Wang and Haiyang Xue},
      title = {Linear-Communication {ACSS} with Guaranteed Termination and Lower Amortized Bound},
      howpublished = {Cryptology {ePrint} Archive, Paper 2026/304},
      year = {2026},
      url = {https://eprint.iacr.org/2026/304}
}