Fully Secure DKG

At the upcoming CRYPTO 2024 conference in Santa Barbara, we will present a new DKG protocol as part of the paper “Round-Optimal Fully Secure Distributed Key Generation”. This work addresses the complexities of distributed key generation (DKG) in cryptographic systems, a critical area for securing digital communications and transactions.

DKG protocols are essential for cryptographic systems where a secret key is shared among multiple parties. They enable parties to securely generate a shared cryptographic key, thus enabling secure operations while preventing compromised parties from gaining useful information. Key applications include securing cryptocurrency wallets, threshold access control, and random beacons.

Achieving full security in DKG has been challenging. Most protocols either allow adversaries to influence the key that is generated or are not robust against malicious disruptions. Fully secure DKG protocols prevent adversaries from biasing the key and ensure the process always completes successfully.

Abstract of the paper

Protocols for distributed threshold key generation (DKG) in the discrete-logarithm setting have gained significant attention recently. Many synchronous DKG protocols have been proposed, but most are not fully secure. These protocols often either allow corrupted parties to influence the key or lack robustness, enabling malicious parties to disrupt the key generation process.

We examine the round complexity of fully secure DKG in settings where an honest majority is feasible. We demonstrate that one-round, unbiased DKG protocols are impossible, even with weaker security notions and without any prior setup. However, we also present various round-optimal protocols for fully secure DKG, highlighting tradeoffs in efficiency, necessary setup, and required assumptions.

Key contributions of the paper

1. Impossibility of One-Round DKG: The paper proves that it is impossible to have a one-round, statistically unbiased DKG protocol. 
2. Round-Optimal Protocols: We present several round-optimal protocols for fully secure DKG, offering different tradeoffs in terms of efficiency, necessary setup, and cryptographic assumptions. These protocols are secure against malicious adversaries and ensure robustness.
3. Efficiency and Practicality: Some of the proposed protocols are highly efficient for small values of n typically used in practice. This makes them competitive choices for real-world applications of DKG.
4. Adaptive Security: We also describe a protocol that remains secure even when adversaries can adaptively decide which parties to compromise based on observed data, further enhancing the security of the key generation process.

This paper sets a new standard for DKG protocols, providing practical solutions that ensure both security and efficiency. By addressing the limitations of previous protocols and proving new theoretical results, it opens the door for more secure and robust cryptographic systems.

We hope the insights and methodologies will  influence future research and development in cryptography, especially in secure multiparty computations and distributed systems.

References

• Round Optimal Fully Secure Distributed Key Generation