Secret sharing is a method by which a secret is split among a group, and requires certain threshold to meet where the members combine their respective shares for the secret to be reconstructed again.

Moreover, when a dealer distributes shares to players in such a way that at least contributions are required to reconstruct the secret back, such a protocol is known as Threshold Secret Sharing

Any secret sharing protocol has two methods: , where:

  • : dealer splits the secret and distributes individual shares to each member.
  • : members combine their shares to reconstruct the secret back.

Properties as explained here:

  • Binding: once share is completed honestly, then there exists a value such that output of reconstruct is equal to .
  • Validity: if dealer distributes secret and perform share honestly, then value of reconstruct is equal to .
  • Hiding: if dealer is honest and no party hash begun reconstruct, then adversary can’t gain any information about .

Secure vs insecure secret sharing

When amount of work required to reconstruct the share isn’t affected by having knowledge of amount of shares, where , then the scheme is deemed as secure.

Let’s take an example of insecure sharing scheme: let the secret consists of 10 bit key, and dealer distributes it to 5 members, each having 2 bits. Any external member with no knowledge will need guesses to get the key, while any 1 member will need and any member with k shares will only require guesses.

Now, let’s define secure secret sharing. Let the secret be and suppose dealer hash to distribute this secret to members. Dealer samples uniformly such that , and distribute these shares to members. To reconstruct back, all shares are needed such that .

TSS

Shamir Secret Sharing is a type of (t, n) threshold secret sharing where a degree polynomial is created and it’s evaluation on n points are shared with the members. Dealer has a secret which it wants to secretly share, it samples uniform elements such that , such that .

  • Generating polynomial of degree over a finite field
  • generating distinct shares:

Polynomial is of the form:

These coefficients are randomly sampled and the points are generated which are the shares.

reconstruct

To reconstruct the share back, any users can pool their shares, and use Lagrange polynomial interpolation to create the polynomial, evaluating it at , will give the original share.

math4.png

Putting , gives us

Note that using integer domain here, compromises security of SSS, as then the adversary start gaining knowledge about the secret with each new share. That's why we use finite field with .

Things to prove:

  1. existence and uniqueness of Lagrange polynomial such that , where is the Lagrange polynomial.
  2. prove that map proven above, for is a bijection of set of degree polynomials to their evaluations at the points in .
  3. prove binding, validity of SSS.
  4. prove hiding of SSS.

I am going to explain again the hiding property of SSS, but has a more formal description here, because it’s really interesting to define.

  • Let’s take an adversary that passively control parties . This means adversary have access to their shares, i.e. .
  • our claim is that maps the uniform distribution of to .
  • Since, we know that honest dealer samples uniformly, then probability of , being any elements, is equal to .
  • we need to show
  • this can be shown using which is a bijection from . Thus, distribution also follows from that.
  • Now, since adversary doesn’t have knowledge of which is , distribution of adversary doesn’t change on the value of the secret. This means, whatever knowledge adversary gains from control of the members, it’s distribution isn’t affected by the secret value.

Pitfalls

  • Zero-share: Common pitfalls occur during share generation as any shareholder who gets has its share as , thus revealing the secret.
  • Non-unique shares: when generating secret back, the protocol needs to evaluate , and if , then doesn’t exist and protocol fails.

References