Adi Shamir published "How to share a secret" [1] in the Communications of the ACM in 1979 and it has since become a classic method in cryptography. 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 an any 3-from-4, we can use a quadratic equation, such as \(f(x)=20 x^2 - 2 x + 10\), and where the value of 10 is the secret. Bob then gets the value of \(f(x)\) when \(x=0\). This can be 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 point on the quadratic equation, and three of them can bring then back to recover the secret. In this case we will generate a random polynomial of \(a x^2 + b x + secret\), and then distribute the shares to Bob, Alice, Carol and Dave. Finally we will recover the secret from three of these shares (Bob, Carol and Dave). In this case, we will use elliptic curves to map the shares.
Shamir Secret Shares with CIRCL and Elliptic Curves |
Background
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)=20 x^2 - 2 x + 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-co-ordinate 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-co-ordinate value, so that when we reconstruct, we know the \(x\)-co-ordinate for the share:
== Secret shares == 2 from 3 === 00000001a971463eae26ff1dc6dd19db77f209643fe72ee384101f6e2bd6e97674ef630c 000000022faa84e5c3a2756b3b3accdbabe548eb67ea81283296913ae9d0fdd45ca25a0d 00000003b5e2c28cd91eecb8b0967edcdfd8877290edd46ddf1b0407a7cb11334555510e =================
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. First we will 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_1 x + p_2 x^2 + ...\)
and where \(p_0\), \(p_1\) and so on, are co-efficients 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\):
Coding
Now we can use the CIRCL 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):
package main import ( "os" "fmt" "crypto/rand" "strconv" "github.com/cloudflare/circl/group" "github.com/cloudflare/circl/secretsharing" ) func main() { tval:=2 nval:=5 curvetype:="P256" g := group.P256 argCount := len(os.Args[1:]) if argCount > 0 { tval,_ = strconv.Atoi(os.Args[1]) } if argCount > 1 { nval,_ = strconv.Atoi(os.Args[2]) } if argCount > 2 { curvetype = (os.Args[3]) } t := uint(tval) n := uint(nval) if (curvetype=="P384") { g = group.P384 } if (curvetype=="P521") { g = group.P521 } secret := g.RandomScalar(rand.Reader) ss := secretsharing.New(rand.Reader, t, secret) shares := ss.Share(n) fmt.Printf("Secret: %v\n", secret) fmt.Printf("Shares: %v\n", shares) got, err := secretsharing.Recover(t, shares[:t+1]) fmt.Printf("\nWith %d shares: %v\n\n", t,got) got, err = secretsharing.Recover(t, shares[:t]) fmt.Printf("With %d shares: Error: %v\n", t-1, err) }
A sample run for any 4 from 6:
Secret: 0x4036dd49aff1928b51a6134c01dd56940b4aca9bb5322c6f8f7b65c01a04ab0b Shares: [{0x0000000000000000000000000000000000000000000000000000000000000001 0x6bd470a4abb2de635647ff421f4d21e40699506ed0613f3c7075f46d4d8dfba6} {0x0000000000000000000000000000000000000000000000000000000000000002 0x712aca51db653c237c2a8904ab6882243f59b842c59f6a5b4653d7ffbf6fd83a} {0x0000000000000000000000000000000000000000000000000000000000000003 0x406a87e2e7de2487f80b14c10202d16491ca200981084921aceb89ae47d7a838} {0x0000000000000000000000000000000000000000000000000000000000000004 0x1c6b4ad092c4269ee9787f08d33163a218b3ad072910da7edb4aab31e82ae9a8} {0x0000000000000000000000000000000000000000000000000000000000000005 0x9aabb87ab68ee7c85ad31cd2234b86c72d6a8bd21e8780fba3b606c5cb073129} {0x0000000000000000000000000000000000000000000000000000000000000006 0xa3517a2a468723b4414cbb774aea82abedfffaf7ae64c5b08c35f9a14b7bdf4f}] With 4 shares: 0x4036dd49aff1928b51a6134c01dd56940b4aca9bb5322c6f8f7b65c01a04ab0b With 3 shares: Error: secretsharing: number of shares (n=4) must be above the threshold (t=4)
References
[1] Shamir, A. (1979). How to share a secret. Communications of the ACM, 22(11), 612–613 [here].