  We give a protocol for Asynchronous Distributed Key Generation (A-DKG) that
is optimally resilient (can withstand $f<\frac{n}{3}$ faulty parties), has a
constant expected number of rounds, has $\tilde{O}(n^3)$ expected communication
complexity, and assumes only the existence of a PKI. Prior to our work, the
best A-DKG protocols required $\Omega(n)$ expected number of rounds, and
$\Omega(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.
