# 3.4: Shamir Secret Sharing

Part of the challenge in designing a secret-sharing scheme is making sure that any authorized set of users can reconstruct the secret. We have just seen that any $$d + 1$$ points on a degree-d polynomial are enough to reconstruct the polynomial. So a natural approach for secret sharing is to let each user’s share be a point on a polynomial.

That’s exactly what Shamir secret sharing does. To share a secret $$m\in \mathbb{Z}_p$$ with threshold $$t$$, we choose a degree-$$(t − 1)$$ polynomial ? that satisfies ?(0) ≡p m, with all other coefficients chosen uniformly in $$\mathbb{Z}_p$$. The ith user receives the point $$(i, ?(i)\%p)$$ on the polynomial. The interpolation theorem shows that any $$t$$ shares can uniquely determine the polynomial ?, and hence recover the secret $$?(0) \equiv_p m$$.

### Construction $$\PageIndex{1}$$ : Shamir SSS

Correctness follows from the interpolation theorem. To show the scheme’s security, we first show a convenient lemma about the distribution of shares in an unauthorized set:

### Lemma $$\PageIndex{1}$$

Let $$p$$ be a prime and define $$\mathbb{Z} _ { p } ^ { + } \stackrel{\text{def}}{=} \mathbb{Z} _ { p } | \{ 0 \}$$. Then following two libraries are interchangeable:

In other words, if we evaluate a uniformly chosen degree $$t − 1$$ polynomial on fewer than t points, the results are (jointly) uniformly distributed.

#### Proof:

We will prove the lemma here for the special case where the calling program always provides a set $$U$$ with $$|U| = t − 1$$. Exercise 3.5 deals with the more general case.

Fix a message $$m \in \mathbb{Z}_p$$, fix set $$U$$ of users with $$|U| = t − 1$$, and for each $$i \in U$$ fix a value $$y_i \in \mathbb{Z}_p$$. We wish to consider the probability that a call to QUERY($$m,t,U$$) outputs $$((i,y_i))_{i \in U}$$, in each of the two libraries.

In library $$\mathscr { L } _ { \text { ssss-rand } }$$, this event happens with probability $$1/p^{t − 1}$$ since QUERY chooses the $$t − 1$$ different yi values uniformly in $$\mathbb{Z}_p$$.

In library ℒssss-real, the event happens if and only if the degree-$$(t − 1)$$ polynomial $$?(x)$$ chosen by QUERY happens to pass through the set of points $$? = \{(i,y_i) | i \in U \} \cup \{(0,m)\}$$. These are t points with distinct x-coordinates, so by Theorem 3.3.1 there is a unique degree-$$(t − 1)$$ polynomial ? with coefficients in $$\mathbb{Z}_p$$ passing through these points.

The QUERY subroutine picks ? uniformly from the set of degree-$$(t − 1)$$ polynomials satisfying $$?(0) \equiv_p m$$, of which there are pt−1. Exactly one such polynomial causes the event in question, so the probability of the event is $$1/p^{t − 1}$$.

Since the two libraries assign the same probability to all outcomes, we have $$\mathscr{L}_{\text{ssss-real}} \equiv \mathscr{L}_{\text{ssss-rand}}$$.

### Theorem $$\PageIndex{1}$$ :

Shamir’s secret-sharing scheme (Construction $$\PageIndex{1}$$) is secure according to Definition 3.1.2.

### Proof:

Let S denote the Shamir secret-sharing scheme. We prove that $$\mathscr{L}^{\text{S}}_{\text{tsss-L}} \equiv \mathscr{L}^{\text{S}}_{\text{tsss-R}}$$ via a hybrid argument.

Our starting point is $$\mathscr{L}^{\text{S}}_{\text{tsss-L}}$$, shown here with the details of Shamir secret-sharing filled in.

Almost the entire body of the QUERY subroutine has been factored out in terms of the $$\mathscr{L}_{\text{ssss-real}}$$ library defined above. The only thing remaining is the “choice” of whether to share $$m_L$$ or $$m_R$$. Restructuring the code in this way has no effect on the library’s behavior.

By Lemma $$\PageIndex{1}$$ , we can replace ℒssss-real with ℒssss-rand, having no effect on the library’s behavior.

The argument to QUERY’ has been changed from $$m_L$$ to $$m_R$$. This has no effect on the library’s behavior, since QUERY’ is actually ignoring its argument in these hybrids.

Applying the same steps in reverse, we can replace $$\mathscr{L}_{\text{ssss-rand}}$$ with $$\mathscr{L}_{\text{ssss-real}}$$, having no effect on the library’s behavior.

A subroutine has been inlined, which has no effect on the library’s behavior. The resulting library is $$\mathscr{L}^{\text{S}}_{\text{tsss-R}}$$.

We showed that $$\mathscr{L}^{\text{S}}_{\text{tsss-L}} \equiv \mathscr{L}_{\text{hyb-1}} \equiv · · · \equiv \mathscr{L}_{\text{hyb-4}} \equiv \mathscr{L}^{\text{S}}_{\text{tsss-r}}$$, so Shamir’s secret sharing scheme is secure.