Shamir's Secret Sharing Schemes

Let $\mathcal{M}$ be some data domain, indexed from $0$ to $|\mathcal{M}| - 1$, and assume $n, t \in \mathbb{N}^+$ such that $t \le n$.

Problem. Distribute a secret $m \in \mathcal{M}$ among $n$ parties $P_1, \ldots, P_n$ such that any subset of at least $t$ parties, termed an authorized subset, can reconstruct $m$, whereas any subset with fewer than $t$ parties cannot.

Shamir's Idea: Use polynomials!

Encoding

Encoding Algorithm (Share $m$):

1. Choose a prime number $p$, s.t., $p \ge \max \{n, |\mathcal{M}| \}$.
2. Generate independent uniform random integers $a_1, \ldots, a_{t - 1} \in \mathbb{F}_p$, and let $a_0 = m$.
3. Construct Polynomial $f(x) = a_{t - 1} x^{t - 1} + a_{t - 2} x^{t - 2} + \cdots + m$, s.t.,$$f(0) = a_0 = m.$$
4. Compute $s_i = f(i), \forall i \in [n]$. Output $(s_1, \ldots, s_n)$, i.e., distribute $s_i$ to party $P_i$.

Security

It is easy to see that any subset of size $< t$ can not reconstruct $a_0 = m$.

Theorem. Given $m, c_1, \ldots, c_{t - 1} \in \mathbb{F}_p$, it holds that

$$\Pr \left[ s_1 = c_1, s_{t - 1} = c_{t - 1} \right] = \frac{1}{p^{t - 1}}.$$

By symmetry, it is easy to see this theorem applies to arbitrary size-$(t - 1)$ subset of $(s_1, \ldots, s_n)$.

Proof. The unknown vector $(a_{t - 1}, \ldots, a_1)$ satisfies the following linear system:

i.e.,

which can be solved efficiently as the first matrix is a Vandermonde one.

$\square$

Decoding

As for reconstruction, assume without loss of generality, the input is $s_1, \ldots, s_t$.

Reconstruct ( $s_1, \ldots, s_t$ ):
The unknown vector $(a_{t - 1}, \ldots, a_0)$ can be reconstructed from the following linear system:

$$\begin{bmatrix} 1& 1& \cdots, 1 \\ 2^{t - 1}& 2^{t - 2}& \cdots, 1 \\ & \vdots \\ t^{t - 1}& t^{t - 2}& \cdots, 1 \end{bmatrix} \begin{bmatrix} a_{t - 1} \\ a_{t - 2} \\ \vdots \\ a_0 \end{bmatrix} = \begin{bmatrix} s_1 \\ s_2 \\ \vdots \\ s_t \end{bmatrix}.$$

Note. Fast reconstruction is possible, as the first matrix is a Vandermonde matrix.

After knowing $a_{t - 1}, \ldots, a_0$, we can recover all $s_1, \ldots, s_n$.

Remark. The encoding and decoding scheme is akin to Reed-Solomon Codes.

Remark. It is possible to corrupt fewer than $\frac{p - t + 1}{2}$ of $(s_1, \ldots, s_n)$ and still be able to decode.

Reference

[1] Note by Yael Kalai “Secret Sharing Schemes”.