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 1987, Paul Feldman published a paper which proposed using the homomorphic encryption properties of exponation to create verifiable shares, and where a dealer creates the secret shares and distributed them to the players. They also publish an overall commitment to the shares and where each player can check that their share is valid, without revealing any information about the secret share, and any other player's secret share.
Feldman Verifiable Secret Sharing Scheme using Kryptology |
Background
Who do we trust on the Internet? Basically, no-one. And so we need to integrate trust into every part of our digital world, as we never know who and what is being dishonest. In a card game, we might have a cheating player, or a player that refuses to show their cards to the other players. But what about a dishonest dealer? How do we detect that?
Well, one way is to share a secret, and then distribute it to the players. The players will then only be able to recover the secret when a given number of them reach a threshold. This can be defined as an any t-from-n scheme. This approach was perfected by Adi Shamir, and who created the Shamir Secret Sharing (SSS) system. But what about a dishonest dealer? How do the entities who receive the shares verify that they are valid? Well one of the best ways was developed by Paul Feldman and is defined as a Verfiable Secret Sharing (VSS) method [1]. The great advantage of this method is that we can use any homomorphic encryption approach.
For this we create a group \(G\) using a prime number \(p\) and a generator \(g\) (typically a value of \(g=2\) or \(g=5\) is used). Overall the dealer creates a secret (\(s\)) and a random polynomial (\(f(x)\)), and where \(f(0)=s\). For example:
\(f(x) = 5 + 2x + 4x^2\)
in this case, the secret is 5, and \(f(1)\) is 7, f(2) is 25, \(f(3)\) is 47 and \(f(4)\) is 77. For any 3-from-4 we can distribute points (1,7), (2,25), (3,47) and (4,77) to each of the players. Each player gets one point on the curve. With three points the players will then be able to discover the quadradic equation, and reveal the secret. With just one or two points, it will be impossible to do this. This is at the core of the Shamir method. But how do the players know they are getting a valid share of the secret, without revealing the secret? Well we have:
\(f(x) = s + a_1 x + a_2 x^2 + ...\)
We can then create commitments as:
\(c_0 = g^s \pmod p\)
\(c_1 = g^{a_1} \pmod p\)
\(c_2 = g^{a_2} \pmod p\)
It is then possible for every player \(i\) to verify that:
\(v = f(i) \pmod p\)
and check:
\( \displaystyle g^{v}=c_{0}c_{1}^{i}c_{2}^{i^{2}}\cdots c_{t}^{i^{t}}=\prod _{j=0}^{t}c_{j}^{i^{j}}=\prod _{j=0}^{t}g^{a_{j}i^{j}}=g^{\sum _{j=0}^{t}a_{j}i^{j}}=g^{f(i)}\)
This operation is also done using \(\pmod p\).
Coding
We can use the Kryptology library developed by Coinbase to implement Felman Verifiable Shamir Secret (VSS) Shares. In this case we will define \(t\) for the threshold and \(n\) for the number of shares:
package main import ( crand "crypto/rand" "fmt" "os" "strconv" "strings" "github.com/coinbase/kryptology/pkg/core/curves" "github.com/coinbase/kryptology/pkg/sharing" ) func getCurve(t string) *curves.Curve { s := strings.ToLower(t) if s == "ed25519" { return (curves.ED25519()) } else if s == "k256" { return (curves.K256()) } else if s == "p256" { return (curves.P256()) } else if s == "pallas" { return (curves.PALLAS()) } return curves.ED25519() } func main() { msg := "Hello" var t uint32 = uint32(3) var n uint32 = uint32(5) testCurve := curves.ED25519() 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) } } if argCount > 3 { curvetype := os.Args[4] testCurve = getCurve(curvetype) } scheme, _ := sharing.NewFeldman(t, n, testCurve) secret := testCurve.Scalar.Hash([]byte(msg)) fmt.Printf("=== Feldman Verifiable Secret Shares ===\n") fmt.Printf("Curve: %s\n", testCurve.Name) fmt.Printf("\nMessage: %s\nScheme: %d from %d\nOriginal secret: %x\n", msg, t, n, secret.Bytes()) fmt.Printf("\nSplitting shares:\n") verifiers, shares, _ := scheme.Split(secret, crand.Reader) for _, s := range shares { rtn := verifiers.Verify(s) if rtn == nil { fmt.Printf(" Share %d: %x [Valid]\n", s.Id, s.Bytes()) } } fmt.Printf("\nNow combining with all the shares ...\n") rSecret, err := scheme.Combine(shares...) if err == nil { fmt.Printf("Recovered secret: %x\n", rSecret.Bytes()) } else { fmt.Printf("Cannot recover from all shares\n") } fmt.Printf("\nNow combining with two shares ...\n") rSecret, err = scheme.Combine(shares[0], shares[1]) if err == nil { fmt.Printf("Recovered secret: %x\n", rSecret.Bytes()) fmt.Printf("\nNow combining with two shares ...\n") } else { fmt.Printf("Cannot recover from two shares\n") } fmt.Printf("\nNow combining with three shares ...\n") rSecret, err = scheme.Combine(shares[0], shares[1], shares[2]) if err == nil { fmt.Printf("Recovered secret: %x\n", rSecret.Bytes()) } else { fmt.Printf("Cannot recover from three shares\n") } }
A sample run:
=== Feldman Verifiable Secret Shares === Curve: secp256k1 Message: hello Scheme: 3 from 5 Original secret: 698850c6be29113f9af4d12fa1702a737d6f277b8356a8fdfcaad8b2f84eeee4 Splitting shares: Share 1: 00000001841e8c05056a1817a4d9cffe98365bf5ad0fc215704ac468767762b961b26853 [Valid] Share 2: 00000002e890d9c714e882c0acbc876683697a4094842f9c87d21e99d2a2d67752e68dac [Valid] Share 3: 0000000396df3a0ceca4513ab29cf76763098555791d932a1aa41756515ad55ffbb51dae [Valid] Share 4: 000000048f09acd68c9d8385b67b200137167d33158ac9a4d8094ed9b271be002c54599a [Valid] Share 5: 00000005d1103223f4d419a1b8570133ff9061d969cbd30cc001c523f5e79057e4c44170 [Valid] Now combining with all the shares ... Recovered secret: 698850c6be29113f9af4d12fa1702a737d6f277b8356a8fdfcaad8b2f84eeee4 Now combining with two shares ... Cannot recover from two shares Now combining with three shares ... Recovered secret: 698850c6be29113f9af4d12fa1702a737d6f277b8356a8fdfcaad8b2f84eeee4
Coding
Reference
[1 Feldman, P. (1987, October). A practical scheme for non-interactive verifiable secret sharing. In 28th Annual Symposium on Foundations of Computer Science (sfcs 1987) (pp. 427-438). IEEE.