Secret Sharing

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 $n$ players in such a way that at least $t(\text{threshold})$ contributions are required to reconstruct the secret back, such a protocol is known as Threshold Secret Sharing $(t,n)$

Any secret sharing protocol has two methods: $(\text{Share, Reconstruct})$, where:

• $\text{Share}$: dealer splits the secret and distributes individual shares to each member.
• $\text{Reconstruct}$: members combine their shares to reconstruct the secret back.

Properties as explained here:

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

Secure vs insecure secret sharing

When amount of work required to reconstruct the share isn’t affected by having knowledge of $0-k$ amount of shares, where $k<t$, 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 $2^{10}$ guesses to get the key, while any 1 member will need $2^8$ and any member with k shares will only require $2^{10-2k}$ guesses.

Now, let’s define secure secret sharing. Let the secret be $s$ and suppose dealer hash to distribute this secret to $N$ members. Dealer samples $s_i\forall i\in [1,N-1]$ uniformly such that $s_N=s\oplus {⨁}_{i=1}^{N-1}{s}_i$, and distribute these shares to $N$ members. To reconstruct $s$ back, all $N$ shares are needed such that $s={⨁}_{i=1}^N{s}_i$.

$(t,n)$ TSS

Shamir Secret Sharing is a type of (t, n) threshold secret sharing where a degree $t-1$ polynomial is created and it’s evaluation on n points are shared with the members. Dealer has a secret $s$ which it wants to secretly share, it samples $t-1$ uniform elements $a_1,a_2,\dots ,a_t\in \mathbb{F}$ such that $f(X)=s+{\sum }_{i=1}^{t-1}{a}_i{X}^i$, such that $f(0)=s$.

• Generating polynomial $f(x)$ of degree $k-1$ over a finite field ${\mathbb{F}}_p$
• generating distinct shares: $s_i=x_i,f(x_i)$

Polynomial is of the form:

$f(x)=S+r_{1}x+\cdots +r_{k-1}{x}^{k-1}$

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

reconstruct

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

Putting $x=0$, gives us $f(0)=S$

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 $|\mathbb{F}|\gg t$.

Things to prove:

1. existence and uniqueness of Lagrange polynomial such that $f(x)={\sum }_{i=1}^n{\mathcal{L}}_i{y}_i$, where ${\mathcal{L}}_i$ is the $i^{th}$ Lagrange polynomial.
2. prove that map proven above, $\varphi (p_0,\dots ,p_f)=(p(z_1),p(z_2),\dots ,p(z_{f+1}))$ for $Z=\{z_1,\dots z_{f+1}\}$ is a bijection of set of degree $f$ polynomials to their evaluations at the points in $Z$.
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 $\mathcal{A}$ that passively control parties $b_1,\dots ,b_f$. This means adversary have access to their shares, i.e. $p(z_1),\dots ,p(z_f)$.
• our claim is that $\varphi$ maps the uniform distribution of $p_0,\dots ,p_f$ to $(p(z_1),\dots ,p(z_{f+1}))$.
• Since, we know that honest dealer samples $p_1,\dots ,p_f$ uniformly, then probability of $p_0,\dots ,p_f=w_0,\dots ,w_f$, $w_i$ being any elements, is equal to ${\left(\frac{1}{|\mathbb{F}|}\right)}^{f+1}$.
• we need to show $Pr[(p(z_0)),p(z_1),\dots ,p(z_f)=(y_0,y_1,\dots ,y_f)]={\left(\frac{1}{|F|}\right)}^{f+1}$
• this can be shown using $\varphi$ which is a bijection from ${\mathbb{F}}^{f+1}\to {\mathbb{F}}^{f+1}$. Thus, distribution also follows from that.
• Now, since adversary doesn’t have knowledge of $p_0$ which is $p(0)=s$, distribution of adversary doesn’t change on the value of the secret. This means, whatever knowledge adversary gains from control of the $f$ 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 $x_i=0$ has its share as $0,S$, thus revealing the secret.
• Non-unique shares: when generating secret back, the protocol needs to evaluate $\frac{x_m}{x_m-x_j}$ , and if $x_m=x_j(modq)$, then $x_m-x_j$ doesn’t exist and protocol fails.

References

• Adi Shamir: How to share a Secret
• Introduction to Modern Cryptography by Jonathan Katz and Yehua Lindell: Section 15.3
• Joy Of Cryptography: Chapter 3
• A graduate course in applied cryptography by Dan Boneh and Victor Shoup: Chapter 22
• Polynomial Secret Sharing and the Lagrange Basis
• zkDocs: SSS