Shamir's Secret Sharing

Shamir 's secret sharing is a 1979 developed by Adi Shamir secret sharing method. With the help of such a method can be a mystery as to several " instances" ( privy ) to share that for the reconstruction of the secret, only a certain subset of these instances is required ( unlike the simple secret sharing, in which all instances are needed ).

Idea of ​​the method

The "dealer" (named after the dealer in a card game ) selects a polynomial of degree and calculates the support of the polynomial. These reference points ( " Shares" ) distributed the dealer to the remaining entities involved. These can then be reconstructed with an interpolation polynomial whose constant term is the secret.

Expiration

The dealer chooses a polynomial

Where the secret is, and which are selected at random. Now the dealer generates values ​​pairs, and distributes these pairs of values ​​to the instances involved. The are public and the ( " Shares" ) must be kept secret.

By the fundamental theorem of algebra is needed value pairs to this polynomial uniquely determined. Therefore, can be compromised to partial secret, without the secret is in danger of being determined. Only when shares are known, it is possible to determine. But this also means that for the determination of the mystery instances must combine their shares to arrive at the secret.

This system is also known as (t, n) threshold scheme ( say, from t n threshold scheme ), since only the total shares are required to reconstruct the secret.

For the reconstruction of an optimized Lagrange interpolation are used:

Reconstruction by means of the Lagrange interpolation

To reconstruct the polynomial one can use the Lagrange interpolation.

Since we are interested only in the constant term, however, it is enough if we consider

Each participant then calculates

And thus has an additive part of the mystery.

It is important that in this calculation and only those included in the formula that are really involved in the interpolation. Are involved, can not be used.

Shamir 's secret sharing modulo p

In cryptography, it is not practical to expect real numbers. Therefore we restrict ourselves to finite fields. The process must be slightly adapted, in this case, by resorting to the modular arithmetic. If we add in the finite field with elements ( prime), each calculation must be done modulo.

The polynomial is now defined below.

In which

Further is calculated as follows

The calculation is analogous for.