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.