TNO MPC Lab - Shamir Secret Sharing

The TNO MPC lab consists of generic software components, procedures, and functionalities developed and maintained on a regular basis to facilitate and aid in the development of MPC solutions. The lab is a cross-project initiative allowing us to integrate and reuse previously developed MPC functionalities to boost the development of new protocols and solutions.

The package shamir is part of the TNO Go Toolbox.

Limitations in (end-)use: the content of this repository may solely be used for applications that comply with international export control laws.

Secret sharing library in Go

This library implements Shamir secret sharing over finite fields and secret sharing over the integers for integers. In addition, facilities are offered to perform computations on shares of secrets.

Shamir secret sharing

For an explanation of Shamir secret sharing over finite fields, refer to Wikipedia.

Suppose you'd like to share a secret 123 over the finite field of integers modulo 7919. You want to have 5 shares of which 4 are needed for reconstruction of the secret. In this case, you choose a sharing degree of 3.

shares := ShareFiniteField(big.NewInt(123), big.NewInt(7919), 3, 5)

You can then reconstruct the secret by saying

secret, err := SecretShareCombine(shares[0:4])
// secret is a big.Int containing 123

Addition of secret shares

If you have two secrets 123 and 456, and you would like to share these and compute the sum 123+456 as a group, you would send share n of 123 and share n of 456 to friend n for 0 < n < 5, and keep shares 0 to yourself. Then each friend (and you) do

sumShareN, err := ShareAdd([]SecretShare{firstShareN, secondShareN})

Then, you may SecretShareCombine the sumShares to recover 579.

Multiplication of secret shares

In the same way, you can compute the product 123*456 by sharing them both and having all of your friends call ShareMul. Note that if your secrets are shared with degree t, you will need at least 2t+1 shares to recover the shared product (k*t+1 shares for a product of k factors). For a group of five friends and two factors, this limits the degree to t = 2.

Secret sharing over the integers

If you share secrets over a finite field, your computations might wrap around. If you do not want this, you can secret share over the integers instead. Note that while Shamir secret sharing is information theoretically secure, sharing over the integers is not, and provides instead a configurable sigma bits of statistical security.

To share 123 over the integers, with 100 bits of statistical security, write

shares := ShareIntegers(big.NewInt(123), big.NewInt(10000), 100, 3, 5)

Here, 10000 is the upper bound on the secret you are sharing.