Fall 2019

Asynchronous Distributed Key Generation

Wednesday, October 23rd, 2019 4:00 pm4:30 pm

Add to Calendar


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.