Skip to main content
Engineering LibreTexts

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

    Screen Shot 2019-02-18 at 1.35.57 AM.png

    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:

    Screen Shot 2019-02-18 at 11.46.24 AM.png

    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.

    Screen Shot 2019-02-18 at 12.24.12 PM.png

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

    Screen Shot 2019-02-18 at 12.27.15 PM.png

    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.

    Screen Shot 2019-02-18 at 12.28.08 PM.png

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

    Screen Shot 2019-02-18 at 12.29.20 PM.png

    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.

    Screen Shot 2019-02-18 at 12.30.10 PM.png

    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.

    Screen Shot 2019-02-18 at 12.31.39 PM.png

    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.