# 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.