Shamir's Secret Sharing

Shamir's Secret Sharing is a secret sharing method developed by Adi Shamir in 1979 . With the help of such a procedure, a secret can be divided among several "instances" (confidants) in such a way that only a certain subset of these instances is required to reconstruct the secret (in contrast to simple secret sharing , in which all instances are required).

Idea of ​​the procedure

The "dealer" (named after the dealer in a card game ) determines a number of instances that should be able to reconstruct the secret later and then selects a polynomial of degree and calculates the polynomial points. The dealer distributes these support points ("shares") to the remaining entities involved. These entities can then use an interpolation method to reconstruct the polynomial, the constant term of which is the secret. ${\displaystyle t}$ ${\displaystyle t-1}$ ${\displaystyle n,n\geq t}$

procedure

The dealer chooses a polynomial

${\displaystyle f(x)=s+a_{1}\cdot x+a_{2}\cdot x^{2}+\dots +a_{t-1}\cdot x^{t-1}}$

where is the secret and which are chosen at random. The dealer now generates pairs of values , and distributes these pairs of values ​​to the entities involved. They are public and the ("shares") must be kept secret. ${\displaystyle s}$ ${\displaystyle a_{i}}$ ${\displaystyle n}$ ${\displaystyle (x_{i},s_{i}=f(x_{i}))}$ ${\displaystyle x_{i}\neq 0}$ ${\displaystyle x_{i}}$ ${\displaystyle s_{i}}$

According to the fundamental theorem of algebra , pairs of values ​​are required to uniquely determine this polynomial. As a result, up to partial secrets can be compromised without the secret being in danger of being determined. Only when shares are known is it possible to determine. However, this also means that in order to determine the secret, instances have to combine their shares in order to get to the secret. ${\displaystyle t}$ ${\displaystyle (x,f(x))}$ ${\displaystyle t-1}$ ${\displaystyle s}$ ${\displaystyle t}$ ${\displaystyle s}$ ${\displaystyle t}$

This system is also referred to as a (t, n) threshold value scheme (read: t out of n threshold value scheme), since only the entire share is required to reconstruct the secret. ${\displaystyle t}$ ${\displaystyle n}$

An optimized Lagrange interpolation can be used to reconstruct : ${\displaystyle s}$

Reconstruction using Lagrange interpolation

Lagrange interpolation can be used to reconstruct the polynomial.

${\displaystyle g(x)=\sum s_{i}\cdot \prod _{j\neq i}{\frac {x-x_{j}}{x_{i}-x_{j}}}}$

But since we are only interested in the constant term , it is sufficient if we consider ${\displaystyle s}$ ${\displaystyle g(0)}$

${\displaystyle s=g(0)=\sum s_{i}\cdot \prod _{j\neq i}{\frac {-x_{j}}{x_{i}-x_{j}}}}$

Each participant now calculates

${\displaystyle w_{i}=s_{i}\cdot \prod _{j\neq i}{\frac {-x_{j}}{x_{i}-x_{j}}}}$

and thereby has an additive part of the secret . ${\displaystyle s=\sum w_{i}}$

It is important that in this calculation only those and are included in the formula that are actually involved in the interpolation. Are involved, may not be used. ${\displaystyle x_{i}}$ ${\displaystyle x_{j}}$ ${\displaystyle i=\{1,6,9\}}$ ${\displaystyle x_{4}}$

Shamir's Secret Sharing modulo p

In cryptography, it is not practical to calculate with real numbers . One therefore restricts oneself to finite bodies . In this case, the procedure has to be adapted slightly by using modular arithmetic. If one calculates in the finite field with elements ( prime ), every calculation must be done modulo . ${\displaystyle p}$ ${\displaystyle p}$ ${\displaystyle p}$

The polynomial is now defined as follows.

${\displaystyle f(x)=s+a_{1}\cdot x+a_{2}\cdot x^{2}+\dots +a_{t-1}\cdot x^{t-1}{\bmod {p}}}$

in which

${\displaystyle 0\leq a_{i},s<p}$

further is calculated as follows ${\displaystyle s}$

${\displaystyle s=g(0)=\sum _{i}\left(s_{i}\cdot \prod _{j\neq i}(-x_{j})(x_{i}-x_{j})^{-1}{\bmod {p}}\right)}$

The calculation for runs analogously. ${\displaystyle w_{i}}$

literature

• Adi Shamir: How to share a secret. (PDF; 194 kB) In: Communications of the ACM . 22, 1979, pp. 612-613.