Distributed key generation
From Wikipedia, the free encyclopedia
Distributed key generation (DKG) is a cryptographic process in which multiple parties contribute to the calculation of a shared public and private key set. Unlike most public key encryption models, distributed key generation does not rely on Trusted Third Parties.[1] Instead, the participation of a threshold of honest parties determines whether a key pair can be computed successfully.[2] Distributed key generation prevents single parties from having access to a private key. The involvement of many parties requires Distributed key generation to ensure secrecy in the presence of malicious contributions to the key calculation.[1]
Distributed key generation is commonly used to decrypt shared ciphertexts or create group digital signatures.[2]
Distributed key generation protocol was first specified by Torben Pedersen in 1991. This first model depended on the security of the Joint-Feldman Protocol for verifiable secret sharing during the secret sharing process.[3]
In 1999, Rosario Gennaro, Stanislaw Jarecki, Hugo Krawczyk, and Tal Rabin produced a series of security proofs demonstrating that Feldman verifiable secret sharing was vulnerable to malicious contributions to Pedersen's distributed key generator that would leak information about the shared private key.[4][5] The same group also proposed an updated distributed key generation scheme preventing malicious contributions from impacting the value of the private key.
Methods
The distributed key generation protocol specified by Gennaro, Jarecki, Krawczyk, and Rabin assumes that a group of players has already been established by an honest party prior to the key generation. It also assumes the communication between parties is synchronous.[5]
- All parties use Pedersen's verifiable secret sharing protocol to share the results of two random polynomial functions.
- Every party then verifies all the shares they received. If verification fails, the recipient broadcasts a complaint for the party whose share failed. Each accused party then broadcasts their shares. Each party then has the opportunity to verify the broadcast shares or disqualify accused parties. All parties generate a common list of non-disqualified parties.
- Each non-disqualified party broadcasts a set of values constructed by raising a common generator to the power of each value used in one polynomial in Part 1.
- These broadcast values are verified by each party similarly to as in Part 2. When a verification fails, the party now broadcasts both the values received in Part 1 and the values received in Part 3. For each party with verifiable complaints, all other parties reconstruct their own value sets in order to eliminate disqualified contributions.
- The group computes the private key as the product of every qualified contribution (each qualified party's random polynomial evaluated at 0).[5]
Avoiding the synchrony assumption
In 2009, Aniket Kate and Ian Goldberg presented a Distributed key generation protocol suitable for use over the Internet.[6] Unlike earlier constructions, this protocol does not require a broadcast channel or the synchronous communication assumption, and a ready-to-use library is available.
Robustness
In many circumstances, a robust distributed key generator is necessary. Robust generator protocols can reconstruct public keys in order to remove malicious shares even if malicious parties still remain in the qualified group during the reconstruction phase.[5] For example, robust multi-party digital signatures can tolerate a number of malicious users roughly proportionate to the length of the modulus used during key generation.[7]
