Shamir's secret sharing

Section 9 Shamir's secret sharing

Subsection 9.1 Basic setup

In 1979 Blakley and Shamir independently introduced the idea of secret sharing. A \((t, n)\) threshold secret sharing scheme is a method for \(n\) parties to distribute a secret such a way that at least \(t\) of them together can reconstruct it. Let us describe the steps of Shamir’s secret sharing scheme. Let \(\mathbb{F}_q\) be a finite field and the secret is \(s\in\mathbb{F}_q.\) We take \(t-1\) random field elements \(a_1,a_2,\ldots,a_{t-1}\) and we define the polynomial

\begin{equation*} f(x)=a_{t-1}x^{t-1}+\ldots+a_1x+s. \end{equation*}

That is we have that the secret is \(f(0).\) The shares \((i,f(i))\) are distributed to the \(n\) distinct parties. To reconstruct the secret we may use a classical algorithm called Lagrange interpolation.

Theorem 9.1. Lagrange interpolation.

Given \(t\) distinct points \((x_i, y_i)\) than there is a polynomial \(f(x)\) of degree less than \(t\) such that \(f(x_i)=y_i.\) The polynomial is as follows

\begin{equation*} f(x)=\sum_{i=1}^t y_i\prod_{\substack{1\leq j\leq t\\i\neq j}}\frac{x-x_j}{x_i-x_j}. \end{equation*}

Subsection 9.2 Example and SageMath implementation

Let us consider a concrete example. We work in the finite field \(\mathbb{F}_{37}\) and suppose that using the shares

\begin{equation*} (3,13),(4,5),(10,6),(13,24),(22,22),(30,31) \end{equation*}

one can reconstruct the secret. We obtain that

\begin{equation*} \begin{aligned} &&f(0)=\frac{13\cdot 4\cdot 10\cdot 13\cdot 22\cdot 30}{(4-3)(10-3)(13-3)(22-3)(30-3)}+\frac{5\cdot 3\cdot 10\cdot 13\cdot 22\cdot 30}{(3-4)(10-4)(13-4)(22-4)(30-4)}+\\ &&\frac{6\cdot 3\cdot 4\cdot 13\cdot 22\cdot 30}{(3-10)(4-10)(13-10)(22-10)(30-10)}+\frac{24\cdot 3\cdot 4\cdot 10\cdot 22\cdot 30}{(3-13)(4-13)(10-13)(22-13)(30-13)}+\\ &&\frac{22\cdot 3\cdot 4\cdot 10\cdot 13\cdot 30}{(3-22)(4-22)(10-22)(13-22)(24-22)}+\frac{31\cdot 3\cdot 4\cdot 10\cdot 13\cdot 22}{(3-31)(4-31)(10-31)(13-31)(22-31)}=\\ &&8.\end{aligned} \end{equation*}

Therefore the secret is 8. We may also apply linear algebra to reconstruct the secret. Since \(t=6\) we need to consider a polynomial of the form

\begin{equation*} f(x)=a_5x^5+a_4x^4+a_3x^3+a_2x^2+a_1x+s. \end{equation*}

The shares yield the system of linear equations

\begin{equation*} \begin{aligned} 31=f(3)&=&a_53^5+a_43^4+a_33^3+a_23^2+a_13+s\\ 5=f(4)&=&a_54^5+a_44^4+a_34^3+a_24^2+a_14+s\\ 6=f(10)&=&a_510^5+a_410^4+a_310^3+a_210^2+a_110+s\\ 24=f(13)&=&a_513^5+a_413^4+a_313^3+a_213^2+a_113+s\\ 22=f(22)&=&a_522^5+a_422^4+a_322^3+a_222^2+a_122+s\\ 31=f(30)&=&a_530^5+a_430^4+a_330^3+a_230^2+a_130+s.\\\end{aligned} \end{equation*}

It follows that

\begin{equation*} \left(\begin{array}{rrrrrr} 1 & 3 & 9 & 27 & 7 & 21 \\ 1 & 4 & 16 & 27 & 34 & 25 \\ 1 & 10 & 26 & 1 & 10 & 26 \\ 1 & 13 & 21 & 14 & 34 & 35 \\ 1 & 22 & 3 & 29 & 9 & 13 \\ 1 & 30 & 12 & 27 & 33 & 28 \end{array}\right) \left(\begin{array}{r} s \\ a_1 \\ a_2 \\ a_3 \\ a_4 \\ a_5 \end{array}\right)= \left(\begin{array}{r} 13 \\ 5 \\ 6 \\ 24 \\ 22 \\ 31 \end{array}\right) \end{equation*}

and the solution is given by \((8, 15, 19, 30, 5, 29).\) Thus the polynomial is \(f(x)=29x^5+5x^4+30x^3+19x^2+15x+8.\) The secret is the constant term, that is 8.

Now we provide a SageMath code to generate appropriate polynomials and shares and also a code to reconstruct the secret from given shares.

Figure 9.2. Shamir's secret sharing

Figure 9.3. Reconstruction

SageMath summary.

cardinality(): Returns the number of elements of a set.
lagrange_polynomial(): Returns the Lagrange polynomial corresponding to some points.
union(): Returns the union of two sets.

Exercises 9.3 Exercises

1.

Use Shamir’s secret sharing to share \(s=19\) over \(\mathbb{F}_{79}\) such that 4 users can reconstruct the secret. Generate at least 6 shares.

2.

Shamir’s secret sharing with \(p= 31.\) We know the following shares and we also know that 3 parties can reconstruct the secret

\begin{equation*} \begin{aligned} S_1=16, && S_4=16,\\ S_2=5, && S_5=7,\\ S_3=5, && S_6=9.\end{aligned} \end{equation*}

Recover the secret by using the shares \(S_1,S_2,S_3\) and \(S_4,S_5,S_6.\)