Can I Use Distributed Key Generation (DKG) and ECDSA Signatures? Yes, with DKLS

Can I Use Distributed Key Generation (DKG) and ECDSA Signatures? Yes, with DKLS

There is a great rise in the usage of DKG (Distributed Key Generation) infrastructures, and where we can split a key into secret shares, and then store these in different locations. When required we can combine the key shares to recreate the secret key. But, can we also do the same for a digital signature, where the parties who hold the key shares can generate a part of the signature, and which can then be combined, without requiring the key to be regenerated.

A threshold digital signature scheme allows a signature to be split up between n parties, and then for at least t of these parties to be combined together to build a digital signature. This is defined as a t-of-n threshold signature scheme. This includes n shares of a secret key (sk). If there are only t-1 shares, it will not be possible to re-create the secret key, and thus we will not be able to sign a message. This provides us with an example of MPC (Multiparty Computation).

ECDSA (Elliptic Curve Digital Signature Algorithm) was selected by Satoshi Nakamoto for Bitcoin and for Ethereum for their digital signatures. It is thus well supported for its usage. Unfortunately, threshold schemes for the ECDSA method are not well supported within the splitting of the secret key. One of the first papers to propose a t-from-n digital signature method for ECDSA was proposed in 2019 by Doerner, Kondi, Lee, and Shelat (DKLS) [1][here]:

In this case, Bob and Alice will communicate using a DKG method, and then Bob will be able to create a valid signature. We can use the Kryptology library developed by Coinbase to implement 2-of-2 threshold ECDSA signing algorithm of the DKLS method. Once Bob and Alice have communicated, Bob will hold a signature for the message. We will then check this signature for its validity. We will use the Krytology library for the code [here]:

package main

import (
	"crypto/ecdsa"
	"crypto/sha256"
	"fmt"
	"os"

	"github.com/btcsuite/btcd/btcec"
	"github.com/coinbase/kryptology/pkg/core/curves"
	"github.com/dustinxie/ecc"

	"github.com/coinbase/kryptology/pkg/tecdsa/dkls"
)

func main() {

	msg := "Hello 123"

	argCount := len(os.Args[1:])

	if argCount > 0 {
		msg = os.Args[1]
	}

	params, _ := dkls.NewParams(btcec.S256(), curves.NewK256Scalar())

	alice := dkls.NewAlice(params)
	bob := dkls.NewBob(params)

	m := []byte(msg)
	digest := sha256.Sum256(m)

	alicePipe, bobPipe := dkls.NewPipeWrappers()
	errors := make(chan error, 2)
	go func() {
		errors <- alice.DKG(alicePipe)
                }()
                go func() {
                errors <- bob.DKG(bobPipe)
	}()
	for i := 0; i < 2; i++ {
		if err := <-errors; err != nil {
			fmt.Printf("Here")
		}
	}

	fmt.Printf("Message to sign: %s\n", msg)
	fmt.Printf("\nAlice Secret Key: %x\n", alice.SkA.Bytes())
	fmt.Printf("Alice Public Key: %x\n", alice.Pk.Bytes())

	fmt.Printf("\nBob Secret Key: %x\n", bob.SkB.Bytes())
	fmt.Printf("Bob Public Key: %x\n", bob.Pk.Bytes())

	errors = make(chan error, 2)
	go func() {
		errors <- alice.Sign(digest[:], alicePipe)
	}()
	go func() {
		errors <- bob.Sign(digest[:], bobPipe)
	}()

	for i := 0; i < 2; i++ {
		if err := <-errors; err != nil {
			fmt.Printf("Signing failed!!!")
		}
	}

	fmt.Printf("Bob Signature: R:%x S:%x\n", bob.Sig.R, bob.Sig.S)

	fmt.Printf("\n=== Now checking with Bob's public key ===\n")
	publicKey := ecdsa.PublicKey{
		Curve: ecc.P256k1(), //secp256k1
		X:     bob.Pk.X,
		Y:     bob.Pk.Y,
	}

	rtn := ecdsa.Verify(&publicKey, digest[:], bob.Sig.R, bob.Sig.S)

	if rtn {
		fmt.Printf("Signature works. Yipee!")
	} else {
		fmt.Printf("Signature does not check out!!!")
	}

}

Initially, we split the secret key into two shares and distribute these to Bob and Alice., and which are stored as bob.SkA and alice.SkB. These will be used to generate a public key that Bob and Alice can use (bob.Pk and alice.Pk). This public key can be used to verify the generated digital signature. The following displays the secret shares and the public key [here]:

fmt.Printf("Message to sign: %s\n", msg)

fmt.Printf("\nAlice Secret Key: %x\n", alice.SkA.Bytes())

fmt.Printf("Alice Public Key: %x\n", alice.Pk.Bytes())

fmt.Printf("\nBob Secret Key: %x\n", bob.SkB.Bytes())

fmt.Printf("Bob Public Key: %x\n", bob.Pk.Bytes())

Bob generates a signature by communicating with Alice through DKG, and where the generated signature has two values: R and S. This is displayed as:

fmt.Printf("Bob Signature: R:%x S:%x\n", bob.Sig.R, bob.Sig.S)

We can then take Bob’s public key (bob.Pk.X and bob.Pk.Y), and then check that this signature is valid against the public key [here]:

fmt.Printf("\n=== Now checking with Bob's public key ===\n")
	publicKey := ecdsa.PublicKey{
		Curve: ecc.P256k1(), //secp256k1
		X:     bob.Pk.X,
		Y:     bob.Pk.Y,
	}

	rtn := ecdsa.Verify(&publicKey, digest[:], bob.Sig.R, bob.Sig.S)

	if rtn {
		fmt.Printf("Signature works. Yipee!")
	} else {
		fmt.Printf("Signature does not check out!!!")
	}

A sample run [here]:

Message to sign: hello 123

Alice Secret Key: 4d8774e7588a7af7886f1d97216bd7cf97bcce0f3ed4b0cc1308eba19d7068ce
Alice Public Key: 8383eb0260d211043e190b4b8a79db1a95ac0f9b6b5e37946e4bf76f4ad733535ccf8a8e48632107b58f8311f1df1580cbfdd80db01ae952435b4897ecf586ef

Bob Secret Key: d099fd0419dc6afb58229ceece9308a89f35d574e6077ccdf41c50b0ce48c0d0
Bob Public Key: 8383eb0260d211043e190b4b8a79db1a95ac0f9b6b5e37946e4bf76f4ad733535ccf8a8e48632107b58f8311f1df1580cbfdd80db01ae952435b4897ecf586ef
Bob Signature: R:bb4c4b4fbba9da07687320e0c2bf95e5eef5471db1b819fd0188b14f4a60362c S:1efc7288269e613e05faaa29370f86b46cf57cb107e41ef3030a4d345dd0a911

=== Now checking with Bob's public key ===
Signature works. Yipee!

Conclusions

ECDSA has been so successful and is playing a core role in building a more trusted digital world. Unfortunately its approach is making the distributed processing of the signature a little difficult. One thing that is for sure, is that the research community will find an ingenious way to overcome this barrier. So, here’s to a digital world which is inherently secure, resilient and trustworthy — by design!

Reference

[1] Doerner, J., Kondi, Y., Lee, E., & Shelat, A. (2019, May). Threshold ECDSA from ECDSA assumptions: the multiparty case. In 2019 IEEE Symposium on Security and Privacy (SP) (pp. 1051–1066). IEEE.

Asecuritysite is provided free and without adverts. If you want to support its development and get access to this blog, subscribe here: