SecretSharing

Invented independently by Adi Shamir and George Blakley in 1979, a $(n,m)$-threshold scheme breaks a secret and shares it with $m$ individuals. While any group of $n$ or more individuals can together reconstruct the secret, no group of fewer than $n$ individuals can obtain any information at all.

• Blakley's scheme
  As any $n$ $(n-1)$-dimensional hyperplanes in ${\mathbb{R}}^n$ intersect at a specific point, the secret may be encoded as any single coordinate of the point of intersection. Each individual secret holder is given enough information (say coefficients of the defining linear equation) to define a hyperplane; the secret is recovered by calculating the point of intersection.
• Shamir's scheme
  One can fit a unique polynomial of degree $n-1$ to any set of $n$ points that lie on the polynomial. The scheme first creates a polynomial $p(x)$ of degree $n-1$ with the secret as the first coefficient and the remaining coefficients picked at random. Then for any $m\ge n$, gets $m$ points $(x_i,p(x_i))$ on the graph of the polynomial, and gives one to each of the individual secret holder. Any $n$ individuals come together will be able to determine $p(x)$ using their shares.

Note that Shamir's scheme can be viewed as a special version of Blakley's scheme. Namely, let $V$ be the vector space of all polynomials of degree at most $n-1$ over $\mathbb{R}$. Thus, $V$ is a vector space of dimension $n$. Let $p(x)$ be the polynomial of degree $n-1$ chosen with $(x_i,y_i=p(x_i))$, $i=1,2,\dots ,n$, picked. For any pair $(x_i,y_i)$, set $V_i=\{f(x)\in V\mid f(x_i)=y_i\}$, which is an affine subspace of $V$ of dimension $n-1$: if $f(x),g(x)\in S_i$ and ${\lambda }_1,{\lambda }_2\in F$ with ${\lambda }_1+{\lambda }_2=1$, then ${\lambda }_{1}f(x)+{\lambda }_{2}g(x)\in S_i$ as well. Now, it is easy to see that ${\cap }_i{S}_i=\{p(x)\}$. If we write $p(x)=c_0+c_{1}x+c_2{x}^2+\cdots +c_{n-1}{x}^{n-1}$, then $p(x_i)=c_0+c_1{x}_i+c_2{x}_i^2+\cdots +c_{n-1}{x}_i^{n-1}$. Thus, we can view $(1,x_i,x_i^2,\dots ,x_i^{n-1})$ as the (specially chosen) coefficients of the defining equation of the hyperplane $t_0+a_1{t}_1+a_2{t}_2+\cdots +a_{n-1}{t}_{n-1}=y_i$ (here $t_j$ are variables and $a_j=x_i^j$, $j=1,\dots ,n-1$) in ${\mathbb{R}}^n$.

For a large secret, one can encrypt the secret using a private key system, and then distribute the key using secret sharing.