Welcome to the resource topic for
**2023/1130**

**Title:**

Perfectly Secure Asynchronous Agreement on a Core Set in Constant Expected Time

**Authors:**
Ittai Abraham, Gilad Asharov, Arpita Patra, Gilad Stern

**Abstract:**

A major challenge of any asynchronous MPC protocol is the need to reach 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 and statistical 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, is perfectly secure, and resilient to t<\frac{n}{4} corruptions. Our solution 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. We show a similar result with statistical security for t<\frac{n}{3}.

**ePrint:**
https://eprint.iacr.org/2023/1130

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

**Example resources include:**
implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .