Towards Large Scale Distributed Key Generation

Abstract

Distributed key generation (DKG) is a cryptographic primitive that produces one public key and shares of a corresponding secret key among a group of distributed parties.

As the basis of threshold cryptography, the classical DKG protocols are resurging due to their widespread applications in blockchain, such as MEV protection, checkpointing into Bitcoin, and more. Those applications raise a challenge of deploying DKG on a very large scale.

While efforts have been made to improve DKG communication, practical large-scale deployments are yet to come due to various issues.

On the other hand, theoretical challenges arise when we aim to optimise the latency while achieving near-optimal communication costs.

This thesis focus on solving scalable DKG on both practical and theoretical landscape.

We first investigate how to build a practical, scalable and adaptively secure DKG protocol to enable all-hands checkpointing in blockchains with weighted validators. Our Any-Trust DKG achieves (quasi-)linear computation and broadcast overhead per-node cost with the help of a common coin, against weak adaptive adversaries. The key to our improvements lies in delegating the most costly operations to an Any-Trust group together with a set of techniques for adaptive security.

Our Any-Trust DKG leads to a fully practical instantiation of Filecoin's checkpointing mechanism, in which all validators of a Proof-of-Stake (PoS) blockchain periodically run DKG and threshold signing to create checkpoints on Bitcoin, to enhance the security of the PoS chain.

Then, on the theoretical side, we purpose Circular Dragon, the first construction of adaptively secure DKG protocol that (i) realises optimal n/2 resilience in the synchronous network, and (ii) attains near-optimal asymptotic complexities, i.e., O(n^2 log n) communication and O(k log n) rounds. In addition, the proposed DKG protocol also produces field-element secrets to support the standard discrete-logarithm based threshold cryptosystem.