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 uniquely 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\), first choose a degree- \((t-1)\) polynomial \(f\) that satisfies \(f(0) \equiv_{p} m\), with all other coefficients chosen uniformly in \(\mathbb{Z}_{p}\). The \(i\) th user receives the point \((i, f(i) \% p)\) on the polynomial. The interpolation theorem says that any \(t\) of the shares can uniquely determine the polynomial \(f\), and hence recover the secret \(f(0)\).

Construction \(3.11\) (Shamir SSS)

 

Correctness follows from the interpolation theorem.

Example

Here is an example of 3-out-of-5 secret sharing over \(\mathbb{Z}_{11}\) (so \(\left.p=11\right)\). Suppose the secret being shared is \(m=7 \in \mathbb{Z}_{11}\). The Share algorithm chooses a random degree-2 polynomial with constant coefficient \(7 .\)

Let’s say that the remaining two coefficients are chosen as \(f_{2}=1\) and \(f_{1}=4\), resulting in the following polynomial:

\[f(x)=1 x^{2}+4 x+7\]

This is the same polynomial illustrated in the previous example:

Figure \(\PageIndex{1}\): Copy and Paste Caption here. (Copyright; author via source)

For each user \(i \in\{1, \ldots, 5\}\), we distribute the share \((i, f(i) \% 11)\). These shares correspond to the highlighted points in the mod-11 picture above.

user \((i)\)	\(f(i)\)	share \((i, f(i) \%\)
1	\(f(1)=12\)	\((1,1)\)
2	\(f(2)=19\)	\((2,8)\)
3	\(f(3)=28\)	\((3,6)\)
4	\(f(4)=39\)	\((4,6)\)
5	\(f(5)=52\)	\((5,8)\)

Remember that this example illustrates just one possible execution of Share. Because Share is a randomized algorithm, there are many valid sharings of the same secret (induced by different choices of the highlighted coefficients in \(f\) ).

Security

To show the security of Shamir secret sharing, we first show a convenient lemma about the distribution of shares in an unauthorized set:

Lemma 3.12 

Let p be a prime and define the following two libraries:

Figure \(\PageIndex{1}\): Copy and Paste Caption here. (Copyright; author via source)

\(\mathcal{L}_{\text {shamir-real }}\) chooses a random degree-( \(\left.t-1\right)\) polynomial that passes through the point \((0, m)\), then evaluates it at the given \(x\)-coordinates (specified by \(U\) ). \(\mathcal{L}_{\text {shamir-rand }}\) simply gives uniformly chosen points, unrelated to any polynomial.

The claim is that these libraries are interchangeable \(: \mathcal{L}_{\text {shamir-real }} \equiv \mathcal{L}_{\text {shamir-rand }}\).

Proof

Fix a message \(m \in \mathbb{Z}_{p}\), fix set \(U\) of users with \(|U|<t\), 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 \(\operatorname{POLY}(m, t, U)\) outputs \(\left\{\left(i, y_{i}\right) \mid i \in U\right\}\), in each of the two libraries. \({ }^{2}\)

In library \(\mathcal{L}_{\text {shamir-real }}\), the subroutine chooses a random degree- \((t-1)\) polynomial \(f\) such that \(f(0) \equiv_{p} m\). From Corollary \(3.10\), we know there are \(p^{t-1}\) such polynomials.

In order for POLY to output points consistent with our chosen \(y_{i}\) ’s, the library must have chosen one of the polynomials that passes through \((0, m)\) and all of the \(\left\{\left(i, y_{i}\right) \mid i \in\right.\) \(U\}\) points. The library must have chosen one of the polynomials that passes through a specific choice of \(|U|+1\) points, and Corollary \(3.10\) tells us that there are \(p^{t-(|U|+1)}\) such polynomials.

The only way for pOLY to give our desired output is for it to choose one of the \(p^{t-(|U|+1)}\) "good" polynomials, out of the \(p^{t-1}\) possibilities. This happens with probability exactly \[\frac{p^{t-|U|-1}}{p^{t-1}}=p^{-|U|}\] Now, in library \(\mathcal{L}_{\text {shamir-rand, POLY chooses its }}|U|\) output values uniformly in \(\mathbb{Z}_{p}\). There are \(p^{|U|}\) ways to choose them. But only one of those ways causes POLY \((m, t, U)\) to output our specific choice of \(\left\{\left(i, y_{i}\right) \mid i \in U\right\}\). Hence, the probability of receiving this output is \(p^{-|U|}\)

For all possible inputs to POLY, both libraries assign the same probability to every possible output. Hence, the libraries are interchangeable.

Theorem \(3.13\)

Theorem 3.13 Shamir’s secret-sharing scheme (Construction 3.11) is secure according to Definition \(3.3 .\)

Proof

Let \(\mathcal{S}\) denote the Shamir secret-sharing scheme. We prove that \(\mathcal{L}_{\mathrm{tsss}-\mathrm{L}}^{\mathcal{S}} \equiv \mathcal{L}_{\mathrm{tsss}-\mathrm{R}}^{\mathcal{S}}\) via a hybrid argument.

Figure \(\PageIndex{1}\): Copy and Paste Caption here. (Copyright; author via source)	Our starting point is \(\mathcal{L}_{\mathrm{tsss}-\mathrm{L}}^{\mathcal{S}}\) shown here with the details of Shamir secret-sharing filled in.
Figure \(\PageIndex{1}\): Copy and Paste Caption here. (Copyright; author via source)	Almost the entire body of the SHARE subroutine has been factored out in terms of the \(\mathcal{L}_{\text {shamir-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.
Figure \(\PageIndex{1}\): Copy and Paste Caption here. (Copyright; author via source)	By Lemma 3.12, we can replace \(\mathcal{L}_{\text {shamir-real with }} \mathcal{L}_{\text {shamir-rand, }}\), having no effect on the library’s behavior.
Figure \(\PageIndex{1}\): Copy and Paste Caption here. (Copyright; author via source)	The argument to POLY has been changed from \(m_{L}\) to \(m_{R}\). This has no effect on the library’s behavior, since POLY is actually ignoring its argument in these hybrids.
Figure \(\PageIndex{1}\): Copy and Paste Caption here. (Copyright; author via source)	Applying the same step in reverse, we can replace \(\mathcal{L}_{\mathrm{shamir-rand}}\) with \(\mathcal{L}_{\mathrm{shamir-real}}\) having no effect on the library's behavior.
Figure \(\PageIndex{1}\): Copy and Paste Caption here. (Copyright; author via source)	A subroutine has been inlined, which has no effect on the library’s behavior. The resulting library is \(\mathcal{L}_{\mathrm{tsss}-\mathrm{R}}{ }^{\mathcal{S}}\)

We showed that \(\mathcal{L}_{\mathrm{tsss}-\mathrm{L}}^{\mathcal{S}} \equiv \mathcal{L}_{\mathrm{hyb}-1} \equiv \cdots \equiv \mathcal{L}_{\mathrm{hyb}-4} \equiv \mathcal{L}_{\mathrm{tsss}-\mathrm{R}}^{\mathcal{S}}\), so Shamir’s secret sharing scheme is secure.

---

\({ }^{2}\) This is similar to how, in Claim 2.7, we fixed a particular \(m\) and \(c\) and computed the probability that \(\operatorname{EAVESDROP}(m)=c\)