# Shamir's Secret Sharing Scheme

Shamir's Secret Sharing Scheme was introduced in [S79] [How to Share a Secret](https://dl.acm.org/doi/pdf/10.1145/359168.359176) by Adi Shamir from MIT.

A secret sharing scheme serves the following goal. A dealer has a secret $\alpha \in Z$ for some finite set $Z$. He wishes to generate $n$ shares $\alpha_1, \dots, \alpha_n \in Z$ such that:

1. Any $t$-sized subset of shares are sufficient to recover $\alpha$.
2. Every subset of size at most $t-1$ does not reveal any information about $\alpha$.

## Defining a Secret Sharing Scheme

We assume there are $n$ parties $P_1, \dots, P_n$ and a dealer, who keeps a secret $\alpha \in Z$, all of which can be modeled as polynomial-time randomized Turing machines.

**Definition.** A **secret sharing scheme** over a finite set $Z$ is a pair of polynomial-time algorithms $(\textsf{Gen}, \textsf{Combine})$:
- $\textsf{Gen}(n, t, \alpha) \to (\alpha_1, \dots, \alpha_n)$: A probabilistic **sharing algorithm** where $0 \leq t \le n$ and $\alpha \in Z$, which generates a $t$-out-of-$n$ sharing of $\alpha$.
- $\textsf{Combine}(T, \{\alpha \}_{i \in T})$: A deterministic **combining algorithm** where $T \subset [n]$ and $|T| = t$, which recovers $\alpha$.

**Definition**. We require **correctness**, that is for every $\alpha \in Z$ and every $t$-sized subset $T$ of $[n]$, we have:

$$\Pr\left[ \textsf{Combine}(T, \{\alpha \}_{i \in T}) = \alpha : (\alpha_1, \dots, \alpha_n) \leftarrow \textsf{Gen}(n, t, \alpha) \right] = 1$$

**Definition**. A secret sharing scheme is **secure** if for every pair $\alpha, \alpha' \in Z$ and $t$-sized subset $T \subset [n]$ we have

$$\{ \alpha_i \}_{i \in T} \approx \{ \alpha'_i \}_{i \in T}$$

That is, the above distributions are (perfectly) indistinguishable.

## Shamir's Secret Sharing Scheme

Shamir introduced a perfectly indistinguishable secret sharing scheme over finite fields of the form $\mathbb{Z}_p$ for a prime $p$ using **polynomial interpolation**. It uses the fact that a polynomial of degree $t - 1$ is exactly determined by $t$ points on the polynomial.

Polynomial interpolation holds for any field, including the real numbers, complex numbers, and finite fields like $\mathbb{Z}_p$ where $p$ is a prime. Informally, a [field](https://en.wikipedia.org/wiki/Field_(mathematics)) is a set for which all non-zero elements have a multiplicative inverse, along with other field axioms.

**Definition.** Shamir's secret sharing scheme is a $t$-out-of-$n$ secret sharing scheme $(\textsf{Gen}, \textsf{Combine})$ over $\mathbb{Z}_q$ (where $q > n$) defined as follows:
- $\textsf{Gen}(n, t, \alpha) \rightarrow (\alpha_1, \dots, \alpha_n)$: Choose $t$ random coefficients $c_1, \dots, c_{t+1} \in \mathbb{Z}_p$ and define the polynomial
$$f(x) = c_1 + c_2 x + \dots + c_{t-1} x \quad \in \mathbb{Z}_p[x].$$
This is equivalent to samping a polynomial $f$ from $\mathbb{Z}_p[x]$ uniformly at random. Then, for $i = 1, \dots, n$, compute $\alpha_i = f(i) \in \mathbb{Z}_p$ and output $(\alpha_1, \dots, \alpha_n)$.
- $\textsf{Combine}(T, \{\alpha_i \}_{i \in T})$: Given $t$ shares, interopolate the polynomial $f$ using Lagrange interpolation and output $f(0) = \alpha$.

## Lagrange Interpolation

Lagrange interpolation for polynomials over finite fields work as follows.

**Lemma.** For every polynomial $f: \mathbb{Z}_p \to \mathbb{Z}_p \in \mathbb{Z}_p[x]$ of degree $t - 1$ and subset $T \subset \mathbb{Z}_p$ of size $|T| = t$ of points $\{ f(i) \}_{i \in T}$ over $f$, we have:

$$f(x) = \sum_{i \in T} \lambda_i(x) f(i)$$

for some $\lambda_i$. That is, very polynomial $f \in \mathbb{Z}_p[x]$ of degree $t-1$ can be interoplated from a $t$-sized set of distinct points over $f$.

**Lemma.** Moreover, we have

$$\lambda_i(x) = \prod_{j \in T \setminus \{i\}} \frac{x - j}{i - j}.$$

Where the $\lambda_i$ are known as the **lagrange interpolation coefficients**.

In particular, note that if $x$ is known in advance (like $x = 0$ as with Sharmir's scheme), then the $\lambda_i$ may be precomputed.

**Remark.** Lagrange interpolation also works over more general finite fields than $\mathbb{Z}_p$.

**Remark.** Shamir's secret sharing is **perfectly secure**, as the distributions $\{\alpha_i\}_{i \in T}$ and $\{\alpha'_i\}_{i \in T}$ are perfectly indistinguishable. This means that the scheme is [information-theoretically secure](https://en.wikipedia.org/wiki/Information-theoretic_security).

## References

- Shamir, Adi. "How to share a secret." Communications of the ACM 22.11 (1979): 612-613.
- P. Feldman, "A practical scheme for non-interactive verifiable secret sharing," 28th Annual Symposium on Foundations of Computer Science (sfcs 1987), Los Angeles, CA, USA, 1987, pp. 427-438, doi: 10.1109/SFCS.1987.4.
- Boneh, Dan and Victor Shoup. "A graduate course in applied cryptography." Draft 0.5 (2020).
- Stadler, Markus. "Publicly verifiable secret sharing." Advances in Cryptology—EUROCRYPT’96: International Conference on the Theory and Application of Cryptographic Techniques Saragossa, Spain, May 12–16, 1996 Proceedings. Berlin, Heidelberg: Springer Berlin Heidelberg, 2001.