Paper 2023/1130

Asynchronous Agreement on a Core Set in Constant Expected Time and More Efficient Asynchronous VSS and MPC

Ittai Abraham, Intel Labs
Gilad Asharov, Bar-Ilan University
Arpita Patra, Indian Institute of Science Bangalore
Gilad Stern, Tel Aviv University

A major challenge of any asynchronous MPC protocol is the need to reach an agreement on the set of private inputs to be used as input for the MPC functionality. Ben-Or, Canetti and Goldreich [STOC 93] call this problem Agreement on a Core Set (ACS) and solve it by running $n$ parallel instances of asynchronous binary Byzantine agreements. To the best of our knowledge, all results in the perfect security setting used this same paradigm for solving ACS. This leads to a fundamental barrier of expected $\Omega(\log n)$ rounds for any asynchronous MPC protocol (even for constant depth circuits). We provide a new solution for Agreement on a Core Set that runs in expected $O(1)$ rounds. Our perfectly secure variant is optimally resilient ($t<n/4$) and requires just $O(n^4\log n)$ expected communication complexity. We show a similar result with statistical security for $t<n/3$. Our ACS is based on a new notion of Asynchronously Validated Asynchronous Byzantine Agreement (AVABA) and new information-theoretic analogs to techniques used in the authenticated model. In addition to the above, we also construct a new perfectly secure packed asynchronous verifiable secret sharing (AVSS) protocol with communication complexity of $O(nX + n^3 \log n)$ for sharing $X$ secrets (of size $O(\log n)$ bits each). The best prior required $O(nX + n^4 \log n)$ for $X$ secrets. AVSS is an important building block for our ACS, and for asynchronous MPC. We improve both communication complexity and round complexity in asynchronous MPC when plugging our new ACS and new AVSS.

Available format(s)
Cryptographic protocols
Publication info
consensusagreement on a core setverifiable secret sharingasynchrony
Contact author(s)
ittai abraham @ intel com
gilad asharov @ biu ac il
arpita @ iisc ac in
gilad stern @ mail huji ac il
2024-02-16: revised
2023-07-20: received
See all versions
Short URL
Creative Commons Attribution


      author = {Ittai Abraham and Gilad Asharov and Arpita Patra and Gilad Stern},
      title = {Asynchronous Agreement on a Core Set in Constant Expected Time and More Efficient Asynchronous VSS and MPC},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1130},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.