# 3.4: Shamir Secret Sharing

- Page ID
- 7330

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.