Photo by Nerene Grobler on Unsplash

Key Distribution Generators using FROST and Kryptology

One of the most important challenges within cybersecurity is key management. This is a way that organisations store encryption keys and can recall them when required. We also need a way to back up these keys, in case we lose them. One method of achieving this is to centralise our key management into a trusted server. This, though, can centralise our infrastructure, and it can become a target for attack.

An alternative is to use a Distributed Key Generation (DKG) infrastructure, and where we split the keys into a number of Shamir shares and then distribute these to a number of stored key stores. This is more secure and also resilient, and where we can create n shares and with a t threshold, and where we can rebuild our data with at least t shares. It should not be possible to reconstruct the key without gathering t shares. In this way, we can either cope with a malicious key store or can cope with an outage on one or more of these.

In this case, we will use the FROST method defined by Komlo and Goldberg [1][here]:

With this, we use a share of a Schnorr signature across trusted parties, and where each of the key shares can be signed by each of the parties, and where the validation signature can only be rebuilt when a given threshold is reached.

Essentially there are two core elements to the FROST method. The first is that n parties run a distributed key generation (DKG) service, and then agree on a verification key, and where each party has its own secret key. Then any one of the parties involved can collaboratively generate a Schnorr signature. In the following diagram, we see that Bob, Alice and Carol have their own secret key. They then create a round where they create a verification key which is the aggregation of their public keys. This uses the Schnorr signature method, and where we can easily aggregate public keys together. The verification key will then be used to verify signatures. Next, we decide what the signing threshold will, and how many signers are allowed to verify a message. In this case, we will do any 2-from-3, and where Bob and Carol can come together and sign for a message:

Implementation

In the following, we will add two new participants to a share: p1 (ID=1) and p2 (ID=2), and where we define an additional participant for p1 as p2 (ID-2), and vice versa. The first argument of NewDkgParticipant is the ID. This is followed by the threshold required to rebuild the shares. The next is the context of the message, and which avoids a replay attack. Finally, we have the curve type (Ed25519), and the last argument is the ID of the other share participant:

Ctx := "Stop reply attack"
testCurve := curves.ED25519()
p1, _ := frost.NewDkgParticipant(1, 2, Ctx, testCurve, 2)
// require.Equal(t, p1.otherParticipantShares[2].Id, uint32(2))
p2, _ := frost.NewDkgParticipant(2, 2, Ctx, testCurve, 1)

After the first round, we have a broadcast value and a p2p share:

bcast1, p2psend1, _ := p1.Round1(nil)
bcast2, p2psend2, _ := p2.Round1(nil)

The ID value of p2psend1 will contain the share (p2psend1 and p2psend2) for the given ID. For example, p2psend1[2] will contain the share for ID=2, and p2psend2[1] will contain the share for ID=1. We can then pass the shares:

bcast := make(map[uint32]*frost.Round1Bcast)
p2p1 := make(map[uint32]*sharing.ShamirShare)
p2p2 := make(map[uint32]*sharing.ShamirShare)
bcast[1] = bcast1
bcast[2] = bcast2
p2p1[2] = p2psend2[1]
p2p2[1] = p2psend1[2]

For this, we exchange the shares, and where the first participant receives the share the second participant:

p1.Round2(bcast, p2p1)
p2.Round2(bcast, p2p2)
fmt.Printf("\nSkShare P1: %x\n", p1.SkShare.Bytes())
fmt.Printf("SkShare P2: %x\n", p2.SkShare.Bytes())
fmt.Printf("\nVerification key P1: %x\n", p1.VerificationKey.ToAffineCompressed())
fmt.Printf("Verification key P2: %x\n", p2.VerificationKey.ToAffineCompressed())

P1 will have a secret key (p1.SkShare), and P2 will also have its own secret key (p2.SkShare). We will now have two verification keys on P1 and P2. These should be the same for each participant. Next, we will split the verification key into any two from three shares:

s, _ := sharing.NewShamir(2, 3, myCurve)

These shares can then be distributed to participants. When we need to rebuild them we:

sk, _ := s.Combine(&sharing.ShamirShare{Id: p1.Id, 
Value: p1.SkShare.Bytes()},&sharing.ShamirShare{Id: p2.Id, 
Value: p2.SkShare.Bytes()})

The value of sk will rebuild the secret back. We can then recreate the verification key with:

vk := myCurve.ScalarBaseMult(sk)
rtn := vk.Equal(p1.VerificationKey)
if rtn {
 fmt.Printf("Verification keys are the same.\n")  
 fmt.Printf("Verification key Round 2: %x\n", vk.ToAffineCompressed())
}

A sample run gives [here]:

SkShare P1: c8669ae1f529a380d63f0fe9a739d1af20773aa1a2b690c5d224c71ebe36b000
SkShare P2: dd7648b5ff76a1f3a85d4572e01d42309980556777da30baa5dbd5907db31d02
Verification key P1: 08c9dc730ae7dbd2b4c8318fb22292f8c3dd877cbd822bb30440861352dcfa15
Verification key P2: 08c9dc730ae7dbd2b4c8318fb22292f8c3dd877cbd822bb30440861352dcfa15
Verification keys are the same.
Verification key Round 2: 08c9dc730ae7dbd2b4c8318fb22292f8c3dd877cbd822bb30440861352dcfa15

Here is the complete code [here]:

package main
import (
"fmt"
"github.com/coinbase/kryptology/pkg/core/curves"
"github.com/coinbase/kryptology/pkg/dkg/frost"
"github.com/coinbase/kryptology/pkg/sharing"
)
// Test dkg round1 works for 2 participants
func main() {
// Round 1
Ctx := "string to prevent replay attack"
myCurve := curves.ED25519()
p1, _ := frost.NewDkgParticipant(1, 2, Ctx, myCurve, 2)
//  require.Equal(t, p1.otherParticipantShares[2].Id, uint32(2))
p2, _ := frost.NewDkgParticipant(2, 2, Ctx, myCurve, 1)
//  require.NoError(t, err)
//  require.Equal(t, p2.otherParticipantShares[1].Id, uint32(1))
bcast1, p2psend1, _ := p1.Round1(nil)
bcast2, p2psend2, _ := p2.Round1(nil)
// Round 2
bcast := make(map[uint32]*frost.Round1Bcast)
p2p1 := make(map[uint32]*sharing.ShamirShare)
p2p2 := make(map[uint32]*sharing.ShamirShare)
bcast[1] = bcast1
bcast[2] = bcast2
p2p1[2] = p2psend2[1]
p2p2[1] = p2psend1[2]
// Running round 2
p1.Round2(bcast, p2p1)
p2.Round2(bcast, p2p2)
fmt.Printf("\nSkShare P1: %x\n", p1.SkShare.Bytes())
fmt.Printf("SkShare P2: %x\n", p2.SkShare.Bytes())
fmt.Printf("\nVerification key P1: %x\n", p1.VerificationKey.ToAffineCompressed())
fmt.Printf("Verification key P2: %x\n", p2.VerificationKey.ToAffineCompressed())
s, _ := sharing.NewShamir(2, 3, myCurve)
sk, _ := s.Combine(&sharing.ShamirShare{Id: p1.Id, Value: p1.SkShare.Bytes()},
&sharing.ShamirShare{Id: p2.Id, Value: p2.SkShare.Bytes()})
vk := myCurve.ScalarBaseMult(sk)
rtn := vk.Equal(p1.VerificationKey)
if rtn {
fmt.Printf("Verification keys are the same.\n")
fmt.Printf("Verification key Round 2: %x\n", vk.ToAffineCompressed())
}
}

Reference

[1] Komlo, C., & Goldberg, I. (2020). FROST: Flexible Round-Optimized Schnorr Threshold Signatures. IACR Cryptol. ePrint Arch., 2020, 852.