Making The Card Game Honest - For The Players and The Dealer: Meet Feldman Verifiable Secret Shares

Making The Card Game Honest - For The Players and The Dealer: Meet Feldman Verifiable Secret Shares

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]. One great advantage of this method is that we can use any homomorphic encryption approach [here]:

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(x0), and where f(0)=s. For example:

f(x) = 5 + 2x + 4x²

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:

We can then create commitments as:

It is then possible for every player i to verify that:

and check:

This operation is also done using (mod p). The dealer thus sends out the commitment (g^v (mod p)) and all the other commitments to the players.

We can use the Kryptology library developed by Coinbase to implement Feldman Verifiable Shamir Secret (VSS) Shares. In this case we will define t for the threshold and n for the number of shares [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(3)
	var n uint32 = uint32(5)
	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)
		}
	}

	testCurve := curves.ED25519()
	scheme, _ := sharing.NewFeldman(t, n, testCurve)

	secret := testCurve.Scalar.Hash([]byte(msg))

	fmt.Printf("=== Feldman Verifiable Secret Shares === ")
	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.Value)
		}

	}

	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 [here]:

=== Feldman Verifiable Secret Shares === 
Message: hello
Scheme: 3 from 5
Original secret: b586c3423482ab97d876ce24cab8bd8ab84e22ac3a52a8dfbb330bbe92a3260f

Splitting shares:
 Share 1: 5e3fb175d1e82cddb5613c7682d544efeb5cf7ddb2cf92eb47613c96ad5dc10a [Valid]
 Share 2: f3649e7834e513292e70fef2889c1f6ffaac38a0b4cd5466fe45b790a5f7fe09 [Valid]
 Share 3: 74f78a4b5d77607b41a2149bdd0d4e0ae43ee6f23f4cee4fdfe17bad7a71df0c [Valid]
 Share 4: f4228191313c007c195b87cba12ff1aba81200d6544b5fa8ea348aec2ccb6203 [Valid]
 Share 5: 4d8f6c04e6f917db62d445ca92f5c67d48288649f3caa76f203fe24dbc04890d [Valid]

Now combining with all the shares ...
Recovered secret: b586c3423482ab97d876ce24cab8bd8ab84e22ac3a52a8dfbb330bbe92a3260f

Now combining with two shares ...
Cannot recover from two shares

Now combining with three shares ...
Recovered secret: b586c3423482ab97d876ce24cab8bd8ab84e22ac3a52a8dfbb330bbe92a3260f

There are many applications of Feldman VSS, but one of the most important is the creation of a distributed key management infrastructure, and where we can split our encryption keys across multiple trusted sites, and then recover them when required. We can build in Byzantien Fault Tolernance into this, as we can cope with a number of failures in the provision of the shares, and also allow the share hosters to check that the shares they have are valid.

Conclusions

We need to build a new digital world, and move away from our centralised and untrusted approaches. The Feldman method is one of the tools we can use in building this new world, and which allows us to become more resilient, while increasing the levels of trust in our digital infrastructure.

References

[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.

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

.