2007 | Rosario Gennaro, Stanislaw Jarecki, Hugo Krawczyk, Tal Rabin
This paper addresses the issue of secure distributed key generation (DKG) for discrete-logarithm-based (dlog-based) cryptosystems. The authors identify a critical flaw in the widely used dlog-based DKG protocol proposed by Pedersen, which does not guarantee a uniformly random distribution of generated keys. They demonstrate an efficient active attacker who can bias the values of the generated keys away from uniform. To address this, they present a new DKG protocol that ensures a uniform distribution of the generated keys. This new protocol is based on ideas similar to Pedersen's but includes a commitment phase using Pedersen's VSS protocol to prevent the attacker from biasing the output distribution. The new protocol is more complex and costly in terms of communication and computation compared to Pedersen's original protocol. However, it provides a secure replacement for applications that require uniform key distribution. The authors also investigate the use of Pedersen's DKG in specific applications with relaxed security requirements, showing that it can be used for certain threshold cryptosystems, such as a threshold Schnorr signature scheme, where the security can be reduced to the hardness of the discrete logarithm problem. The paper concludes with a detailed comparison of the efficiency trade-offs between the new and Pedersen's DKG protocols.This paper addresses the issue of secure distributed key generation (DKG) for discrete-logarithm-based (dlog-based) cryptosystems. The authors identify a critical flaw in the widely used dlog-based DKG protocol proposed by Pedersen, which does not guarantee a uniformly random distribution of generated keys. They demonstrate an efficient active attacker who can bias the values of the generated keys away from uniform. To address this, they present a new DKG protocol that ensures a uniform distribution of the generated keys. This new protocol is based on ideas similar to Pedersen's but includes a commitment phase using Pedersen's VSS protocol to prevent the attacker from biasing the output distribution. The new protocol is more complex and costly in terms of communication and computation compared to Pedersen's original protocol. However, it provides a secure replacement for applications that require uniform key distribution. The authors also investigate the use of Pedersen's DKG in specific applications with relaxed security requirements, showing that it can be used for certain threshold cryptosystems, such as a threshold Schnorr signature scheme, where the security can be reduced to the hardness of the discrete logarithm problem. The paper concludes with a detailed comparison of the efficiency trade-offs between the new and Pedersen's DKG protocols.