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

Ittai Abraham; Gilad Asharov; Arpita Patra; Gilad Stern

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

Abstract

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 parallel instances of asynchronous binary Byzantine agreements. To the best of our knowledge, all results in the perfect and statistical security setting used this same paradigm for solving ACS. Using all known asynchronous binary Byzantine agreement protocols, this type of ACS has expected round complexity, which results in such a bound on the round complexity of asynchronous MPC protocols as well (even for constant depth circuits). We provide a new solution for Agreement on a Core Set that runs in expected rounds. Our perfectly secure variant is optimally resilient () and requires just expected communication complexity. We show a similar result with statistical security for . 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. Along the way, we also construct a new perfectly secure packed asynchronous verifiable secret sharing (AVSS) protocol with just communication complexity, improving the state of the art by a factor of . This leads to a more efficient asynchronous MPC that matches the state-of-the-art synchronous MPC.

Metadata

Available format(s): PDF
Category: Cryptographic protocols
Publication info: A major revision of an IACR publication in TCC 2024
DOI: 10.1007/978-3-031-78023-3_15
Keywords: consensus agreement on a core set verifiable secret sharing asynchrony
Contact author(s): ittai abraham @ intel com
gilad asharov @ biu ac il
arpita @ iisc ac in
gilad stern @ mail huji ac il
History: 2024-12-05: last of 3 revisions; 2023-07-20: received; See all versions
Short URL: https://ia.cr/2023/1130
License: CC BY

BibTeX

@misc{cryptoeprint:2023/1130,
      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},
      doi = {10.1007/978-3-031-78023-3_15},
      url = {https://eprint.iacr.org/2023/1130}
}