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 1991, Torben Pedersen [1] published a paper on "Non-interactive and information-theoretic secure verifiable secret sharing" and which allowed a blinding factor to be used to create verifiable secret shares. With this we can distribute \(n\) shares and where each of the receivers can verify that they have the correct information on the secret [article].
Pedersen Verifiable Secret Sharing Scheme using Kryptology |
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 + ...) G\)
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\):
With Pedersen Verifiable Secret Sharing Scheme (PVSS), we create a blinding factor (\(b\)), and then split this value into co-efficients:
\(g(x) = (b + b_1 x + b_2 x^2 _ ...) H\)
and where \(H\) is a point on the elliptic curve. The dealer (who is distributing the shares) initially privately sends out each share with:
\(S_1=(p(1),g(1))\)
\(S_2=(p(2),g(2))\)
and where the \(p()\) is the secret share, and \(g()\) will be used to verify the share. The dealer then creates a number of commitments for elliptic curve point additions:
\(C_1=p(1)+g(1)\)
\(C_2=p(2)+g(2)\)
and so on. These are then passed to the entities involved.
Each entity which receive a share then checks the commitment against the share elements. If they do not match, the entity will broadcast a complaint to the network, and will reveal the commitment with the shares. The dealer will also reveal their commitment. Next the network will check who is right. If the commitment does not match the share, they will remove the dealer from the network, if not, the will remove the aquising entity from the network.
Coding
We can use the Kryptology library developed by Coinbase to implement Pedersen Verifiable Shamir Secret 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(4) argCount := len(os.Args[1:]) curve := curves.ED25519() 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] curve = getCurve(curvetype) } secret := curve.NewScalar().Hash([]byte(msg)) pt := curve.ScalarBaseMult(secret) pedersen, _ := sharing.NewPedersen(t, n, pt) shares, _ := pedersen.Split(secret, crand.Reader) fmt.Printf("=== Pedersen Verifiable Secret Sharing Scheme === \n") fmt.Printf("Curve: %s\n", curve.Name) fmt.Printf("Msg to hash: %x\n", msg) fmt.Printf("== Secret shares == %d from %d ===\n", t, n) for _, s := range shares.SecretShares { fmt.Printf("Share: %x\n", s.Bytes()) } fmt.Printf("=================\n") fmt.Printf("== Blinding shares == %d from %d ===\n", t, n) for _, s := range shares.BlindingShares { fmt.Printf("Blinding shares: %x\n", s.Bytes()) } fmt.Printf("=================\n") // recovered, _ := pedersen.Combine(shares.SecretShares...) sG, _ := pedersen.Combine(shares.SecretShares...) bH, _ := pedersen.Combine(shares.BlindingShares...) fmt.Printf("Secret: %x\n", secret.Bytes()) fmt.Printf("Recovered: %x\n", sG.Bytes()) fmt.Printf("\nBlinding: %x\n", shares.Blinding.Bytes()) fmt.Printf("Blinding Recovered: %x\n", bH.Bytes()) err := shares.PedersenVerifier.Verify(shares.SecretShares[0], shares.BlindingShares[0]) if err == nil { fmt.Printf("\nShare 1 verified\n") } err = shares.PedersenVerifier.Verify(shares.SecretShares[1], shares.BlindingShares[1]) if err == nil { fmt.Printf("\nShare 2 verified\n") } }
A sample run:
=== Pedersen Verifiable Secret Sharing Scheme === Curve: ed25519 Msg to hash: 68656c6c6f == Secret shares == 3 from 5 === Share: 0000000194d4352814b8614d2fe256582b5d54dc26fe27ea6defd6d6f58adaadf3752401 Share: 00000002cf2422212c33dd9f3a528e1159f600fcb3aae677834c7b49fb1505405d31bc04 Share: 0000000379a392d061900b37242a7dad748ae4d45f545e557b699537ccd48a74cfd5ed09 Share: 00000004a57c91d99a6cdaba15cd2b899f1f20522afb8e82554625a168c76b4b4a63b900 Share: 000000052d580af60b8e6edbbb7489ea96a9719d139f78ff11e32a86d0eda7c4cdd91e09 ================= == Blinding shares == 3 from 5 === Blinding shares: 00000001e2441eb99aca325068faeefdff44a7131f291ef30f4b56a58e90d5d68fcc9702 Blinding shares: 000000020c724fa75cb05cb0121452edf637adc12ca1f3b671ef36e42dabbd7f9e3d010c Blinding shares: 000000031ce8cf64ae9cb89445be7f487039bd494162fda1e83af6383aff10a40f5b9e0a Blinding shares: 00000004ff7a954eaaf25855d7956fb24a43b6c05c6c3bb4742d94a3b38ccf43e3246f0e Blinding shares: 00000005c856aa07364f2b9af1fd2988a75bb9117fbfaded15c710249a53f95e199b7307 ================= Secret: b586c3423482ab97d876ce24cab8bd8ab84e22ac3a52a8dfbb330bbe92a3260f Recovered: b586c3423482ab97d876ce24cab8bd8ab84e22ac3a52a8dfbb330bbe92a3260f Blinding: 780828549db15f24f3aa45c04854696918fa7c56c34d547c5caf58a9e307620e Blinding Recovered: 780828549db15f24f3aa45c04854696918fa7c56c34d547c5caf58a9e307620e Share 1 verified Share 2 verified
Coding
Reference
[1 Pedersen, T. P. (1991, August). Non-interactive and information-theoretic secure verifiable secret sharing. In Annual international cryptology conference (pp. 129-140). Springer, Berlin, Heidelberg.