3.4: Shamir Secret Sharing

Last updated
Save as PDF

Page ID: 7330

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)

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.