The Magic of Shamir Secret Shares and Elliptic Curves

The Magic of Shamir Secret Shares and Elliptic Curves

With secret sharing, we take a secret value and then share it with others. For example, we might have a share for Bob, Alice, Carol and Dave and then for three of them to come together to bring their shares together. For this, we define a threshold (t) and a number of shares (n). We reconstruct the shares we need at least t shares to come together to reveal the secret. If we have (t-1) shares it should be impossible to reconstruct the secret.

For an any 3-from-4, we can use a quadratic equation, such as f(x)=20x²−2x+10, and where the value of 10 is the secret. Bob then gets the value of f(x) when x=0 — and which is defined as f(1). Carol gets f(2), Dave gets f(3) and Alice gets f(4). The secret value is thus f(0). They then each know a y-coordinate point on the quadratic equation. When they want to bring the value back, we can curve fit the gathered points. Thus if we have f(1), f(2) and f(3) we can regenerate the quadratic equation and thus determine f(0). We, of course, need to remember the x co-ordinate values for each share, so we give each share an ID of 1, 2, 3, and so on. Here we have three sample shares from an any 2-from-3 share, and notice that we have the x-coordinate value so that when we reconstruct, we know the x-coordinate for the share:

== Secret shares == 2 from 3 ===
00000001a971463eae26ff1dc6dd19db77f209643fe72ee384101f6e2bd6e97674ef630c 000000022faa84e5c3a2756b3b3accdbabe548eb67ea81283296913ae9d0fdd45ca25a0d 00000003b5e2c28cd91eecb8b0967edcdfd8877290edd46ddf1b0407a7cb11334555510e =================

Elliptic curves

These days we often use elliptic curves to perform efficient operations. With this, we start with a secret (s) and then take the base point of the curve (G) and produce a secret of sG. Next, we convert sG into a number of polynomial factors for a given threshold t and with n shares. We will then take the share point and then split it into a number of polynomial values, and where the point that we cut the y-axis will recover the share. Initially, we will fit a polynomial to the secret with:

P(x)=p_0+p_1x+p_2x²+…

and where p_0, p_1 and so on, are coefficients of the required polynomial. Then we will create the shares for P(1), P(2), and so on. These are the points when x=1, x=2 and so on. These shares can then be distributed to the entities that will store the shares. When required, we gather back at least t shares to recreate the secret (sG). For example, we may use P(0), P(1) … P(t−1) and use a curve fitting method to find P(0) and which is the point of the polynomial where x=0. The value we recover for P(0) is then covered back into an elliptic curve point to give sG:

Now we can use the Kryptology library developed by Coinbase to implement Shamir Secret Shares. In this case, we will define t for the threshold and n for the number of shares. In this case, we will use Ed25519 for our curve, and hash a message to this curve (mysecret) [here]:

package main

import (
	crand "crypto/rand"
	"fmt"
	"os"
	"strconv"

	"github.com/coinbase/kryptology/pkg/core/curves"
	"github.com/coinbase/kryptology/pkg/sharing"
)

func main() {

	msg := "Hello"
	var t uint32 = uint32(2)
	var n uint32 = uint32(3)
	argCount := len(os.Args[1:])

	if argCount > 0 {
		msg = os.Args[1]
	}
	if argCount > 1 {
		val, err := strconv.Atoi(os.Args[2])
		if err == nil {
			t = uint32(val)
		}
	}
	if argCount > 2 {
		val, err := strconv.Atoi(os.Args[3])
		if err == nil {
			n = uint32(val)
		}
	}

	curve := curves.ED25519()
	scheme, _ := sharing.NewShamir(t, n, curve)

	shares, _ := scheme.Split(curve.NewScalar().Hash([]byte(msg)), crand.Reader)

	fmt.Printf("== Secret shares == %d from %d ===\n", t, n)
	for _, s := range shares {
		fmt.Printf("%x ", s.Bytes())
	}
	fmt.Printf("\n=================\n")

	mysecret := curve.NewScalar().Hash([]byte(msg))

	fmt.Printf("Message: %s\n", msg)
	fmt.Printf("\nOriginal Hash: %x\n\n", mysecret.Bytes())

	secret, err := scheme.Combine(shares...)
	if err == nil {
		fmt.Printf("Recorded Hash with all the shares: %x\n", secret.Bytes())
	} else {
		fmt.Printf("Cannot recover with all shares\n")
	}

	secret, err = scheme.Combine(shares[0])
	if err == nil {
		fmt.Printf("Recorded Hash with one share: %x\n", secret.Bytes())
	} else {
		fmt.Printf("Cannot recover with one share\n")
	}

	secret, err = scheme.Combine(shares[0], shares[1])
	if err == nil {
		fmt.Printf("Recorded Hash with two shares: %x\n", secret.Bytes())
	} else {
		fmt.Printf("Cannot recover with two shares\n")
	}

}

A sample run [here]:

== Secret shares == 2 from 3 ===
00000001cdd7b102063bd58b6d785823a686aab5fef297d0820d36d9ef3e2c51bd5ff604
00000002d2fc951ff25611d8d816dac4604e76f544970df5cac8c3d2234a4de4e71bc60a
00000003ea4d84dfc30f3bcc6d1864c33c1c63208b3b8319138451cc57556e7712d89500 
=================
Message: hello

Original Hash: b586c3423482ab97d876ce24cab8bd8ab84e22ac3a52a8dfbb330bbe92a3260f

Recorded Hash with all the shares: b586c3423482ab97d876ce24cab8bd8ab84e22ac3a52a8dfbb330bbe92a3260f
Cannot recover with one share
Recorded Hash with two shares: b586c3423482ab97d876ce24cab8bd8ab84e22ac3a52a8dfbb330bbe92a3260f

Here is a presentation of the method:

In the next article, I will explain how we can now blind these shares using Pedersen Commitments.