Practical Asynchronous High-threshold Distributed Key Generation and Distributed Polynomial Sampling

Distributed Key Generation (DKG) is a technique to bootstrap threshold cryptosystems without a trusted party. DKG is an essential building block to many decentralized protocols such as randomness beacons, threshold signatures, Byzantine consensus, and multiparty computation. While significant progress has been made recently, existing asynchronous DKG constructions are inefficient when the reconstruction threshold is larger than one-third of the total nodes. In this paper, we present a simple and concretely efficient asynchronous DKG (ADKG) protocol among n = 3t + 1 nodes that can tolerate up to t malicious nodes and support any reconstruction threshold ℓ ≥ t. Our protocol has an expected O(κn 3 ) communication cost, where κ is the security parameter, and only assumes the hardness of the Discrete Logarithm. The core ingredient of our ADKG protocol is an asynchronous protocol to secret share a random polynomial of degree ℓ ≥ t, which has other applications, such as asynchronous proactive secret sharing and asynchronous multiparty computation. We implement our high-threshold ADKG protocol and evaluate it using a network of up to 128 geographically distributed nodes. Our evaluation shows that our high-threshold ADKG protocol reduces the running time by 90% and bandwidth usage by 80% over the state-of-the-art. Table 1: Comparison of existing high-threshold ADKG protocols. All of these protocols can tolerate t < n/3 malicious nodes. We measure the computation cost in terms of number of elliptic curve group exponentiations. Abbreviations used are, Decisional Diffie-Hellman (DDH), Symmetric External Diffie-Hellman (SXDH), Decisional Composite Residuosity (DCR), and Discrete Logarithm (DL). Secret key from a Field? High Threshold? Communication Cost (per node) Computation Cost (per node) Total Round Complexity Cryptographic Assumption Setup Assumption Kokoris et al. [39] RO & PKI † These works do not discuss whether their protocols support high-threshold or not. But we believe their protocols can be made to support high-threshold with minor modification. ‡ Their computation cost is O(n 3 ) elliptic curve group operations instead of elliptic curve group exponentiations. Functionality F ADKG Parameters: Maximum number of malicious nodes t, the total number of nodes n ≥ 3t + 1, and the reconstruction threshold ℓ ∈ [t, nt -1]. Let G be an elliptic curve group of order q with a random generator g and scalar field Z q .