New paper on reaching consensus for DKGs under asynchrony.

Today we released a new work on DKGs under asynchrony (here).
The idea is to allow people to reach consensus on the output of a DKG without relying on time-outs. The lead author is Gilad Stern.

Abstract: We give a protocol for Asynchronous Distributed Key Generation (A-DKG) that is optimally resilient (can withstand f< n/3 faulty parties), has a constant expected number of rounds, has O(n^3 log(n)) expected communication complexity, and assumes only the existence of a PKI. Prior to our work, the best A-DKG protocols required O(n) expected number of rounds, and O(n^4) expected communication.

Our A-DKG protocol relies on several building blocks that are of independent interest. We define and design a Proposal Election (PE) protocol that allows parties to retrospectively agree on a valid proposal after enough proposals have been sent from different parties. With constant probability the elected proposal was proposed by a non-faulty party. In building our PE protocol, we design a Verifiable Gather protocol which allows parties to communicate which proposals they have and have not seen in a verifiable manner. The final building block to our A-DKG is a Validated Asynchronous Byzantine Agreement (VABA) protocol. We use our PE protocol to construct a VABA protocol that does not require leaders or an asynchronous DKG setup. Our VABA protocol can be used more generally when it is not possible to use threshold signatures.