5.4 Secret Sharing

Shamir's Secret Sharing Scheme

Shamir’s Secret Sharing Scheme is a method for dividing a secret among a group of people in such a way that only groups of above a certain size can reconstruct the secret.

Let $s\in {\mathbb{F}}_p$ be a secret in the Galois field of some prime $p$, and fix integers $n$ and $k\le n$. The goal is to distribute $n$ shares such that any group of $k$ or more can recover $s$, and any group of fewer than $k$ learns nothing about $s$. To do so:

1. Construct a random polynomial $P(x)\in {\mathbb{F}}_p[x]$ of degree $k-1$, such that
   $P(x)=a_{k-1}{x}^{k-1}+\cdots +a_{1}x+s,$
   where the coefficients $a_i$ are chosen uniformly at random from ${\mathbb{F}}_p$.
2. Distribute the shares $P(1),P(2),\dots ,P(n)$ to $n$ participants. Each participant receives one input-output pair $(i,P(i))$.

To recover the secret, any group of $k$ participants combines their $k$ shares $(x_i,y_i)$ to interpolate the unique degree-$(k-1)$ polynomial $P(x)$ using Lagrange interpolation. The secret is recovered by evaluating $s=P(0)$.

Intuition

Any group with fewer than $k$ shares has fewer than $k$ points on a degree-$(k-1)$ polynomial, so there are infinitely many such polynomials consistent with those shares. These polynomials can produce any value at $x=0$, meaning the secret s remains completely undetermined.

Examples

Secrets in the United Nation

A vault in the United Nations can be opened with a secret combination $s\in \mathbb{Z}$. In only two situations should this vault be opened:

1. All 193 member countries must agree, or

2. At least 55 countries, plus the U.N. Secretary-General, must agree.

Propose a scheme that gives private information to the Secretary-General and all 193 member countries so that the secret combination $s$ can only be recovered under either one of the two specified conditions. Let $P_1(x)=a_{192}{x}^{192}+\dots +a_{1}x+s$, and choose $a_i$'s at random from ${\mathbb{F}}_{193}$. Distribute $P_1(i)$ where $i=1,\dots ,n$ to the $n$ countries, and distribute $P_1(j)$ where $j=n+1,\dots ,n+$ to the Secretary General.

The General Assembly of the UN decides to add an extra level of security: each of the 193 member countries has a delegation of 12 representatives, all of whom must agree in order for that country to help open the vault.

Propose a scheme that adds this new feature.

Trust No One