In this work, we present the first fully asynchronous distributed key generation (ADKG) algorithm as well as the first distributed key generation algorithm that can create keys with a dual (f, 2f+ 1)− threshold that are necessary for scalable consensus (which so far needs a trusted dealer assumption).

In order to create a DKG with a dual (f, 2f+ 1)− threshold we first answer in the affirmative the open question posed by Cachin et al.[8] on how to create an AVSS protocol with recovery thresholds f+ 1< k≤ 2f+ 1, which is of independent interest. Our High-threshold-AVSS (HAVSS) uses an asymmetric bi-variate polynomial, where the secret shared is hidden from any set of k nodes but an honest node that did not participate in the sharing phase can still recover his share with only n− 2f shares, hence be able to contribute in the secret reconstruction. Another building block for ADKG is a novel Eventually Perfect Common Coin (EPCC) abstraction and protocol that enables the participants to create a common coin that might fail to agree at most f+ 1 times (even if invoked a polynomial number of times). Using EPCC we implement an Eventually Efficient Asynchronous Binary Agreement (EEABA) in which each instance takes O (n^2) bits and O (1) rounds in expectation, except for at most f+ 1 instances which may take O (n^4) bits and O (n) rounds in total.