# Distributed Key Generation

Fleeting- Référence externe : https://cronokirby.com/posts/2022/10/dkgs-in-groups/
- Référence externe : https://thork.net/posts/2022_4_21_dkg/

There is some notation confusion whether t-of-n should refer to a minimum of t+1 parties or t parties

similar construction to the threshold signature is the t-of-n multisignature:n parties hold private keysSome trusted entity (eg. a smart contract) collects t+1 unique signatures on some message, (eg. a transaction), and then signs that message itself

a t-of-n threshold signature:Key Generation: Some secret key u, secret to all parties, is constructed. At the end of a DKG, every party possesses some secret share from which u may be reconstructed. No party knows another party’s share.Any t+1 parties can collaborate to sign a message, producing a single signature. No party learns of any other party’s share. The protocol effectively reconstructs the private key, u, in zero knowledge, and uses it to sign a message

centralized setting, a trusted party, Alice, will construct all the shares, and simply send them to the n parties.

Alice is a back door to the threshold signature, as she may simply construct signatures using the private key

Alice can bring her own private key to the threshold signature, where the rest of the threshold signing protocol continues as if Alice were a normal player

emphasize that, in the DKG model, an entirely new secret key is constructed that no player possesses.

, if Alice were to delete her private key, then the setting would be identical to the next section

impossible to verify whether Alice has kept a copy, we turn to cryptography to construct Distributed Key Generation.

DKG proceeds in 3 phases. Participants in the protocol will be called “players”

Phase 1Each player selects their private share, and broadcasts a commitment to it

Phase 2Players first decommit their public keys (broadcasting gui), then perform a secret sharing and determine the group secret sharing.

Phase 3: VerifiabilitySuppose Player Pi were able to lie to player Pj about the value of Xi, the hiding of their secret key share. This would allow player Pi to volunteer to participate in the signing protocol, but prevent the creation of a valid signature, without anyone knowing!

Distributed key generation is a way for a group of people to generate a public key, along with shares of the secret key. These shares should be such that nobody knows the actual secret, and yet further protocols can make use of these shares to do useful operations, such as signing, or decryption.

assume that various problems related to the discrete logarithm in G\mathbb{G}G are hard. In particular, given A=a⋅GA = a ⋅ GA=a⋅G, finding aaa should be intractable.

basic strategy here is linear sharing. We pick shares x1,…,xnx_1, \ldots, x_nx1,…,xn such that ∑ixi=x∑_i x_i = x∑ixi

`x.If we have a trusted third party, then they can be the “dealer”, and the distribute the shares x1,…,xnx_1, \ldots, x_nx1,…,xn, while informing the group of the public key X:=x⋅GX :`

x ⋅ GX:=x⋅G.

how to remove this dealer, so that a group of people can set up a key without needing to trust a third party.

simple idea is that each person can generate their share xix_ixi, which implicitly creates a secret ∑ixi∑_i x_i∑ixi, shared among the participants

person send Xi:=xi⋅GX_i := x_i ⋅ GXi:=xi⋅G to everyone else. You can then sum up these “shares” of the public key, getting X:=∑iXiX := ∑_i X_iX:=∑iXi.

protocol is secure, for honest participants

broken for malicious participants

using a Maurer proof, for the function: φ(x):=x⋅G ϕ(x) := x ⋅ G φ(x):=x⋅G

will force a participant to prove that they know the discrete logarithm

need to have each party set their share before they learn the shares of the other parties

do this using commitments. A commitment hides the value underneath it, but once a commitment is sent, the value hidden underneath can’t be changed

each party send a commitment to their share, and then only after receiving every other commitment will a party reveal their own share