In cryptography, secret sharing refers to any method for distributing a secret amongst a group of participants, each of which is allocated a share of the secret. The secret can only be reconstructed when the shares are combined together; individual shares are of no use on their own.

More formally, in a secret sharing scheme there is one dealer and n players. The dealer gives a secret to the players, but only when specific conditions are fulfilled. The dealer accomplishes this by giving each player a share in such a way that any group of m or more players can together reconstruct the secret but no group of less than m players can. Such a system is called a threshold scheme.

Clipperz adopts Shamir’s secret sharing scheme (SSSS) that was invented by both Adi Shamir (of RSA fame) and George Blakley independently in 1979.

Prof. Adi Shamir, Weizmann Institute of Science

SSSS is based on polynomial interpolation. To allow any m out of n people to construct a given secret, an (m-1)-degree polynomial

f(x) = a₀ + a₁x + … + a_m-1x^m-1

over the finite field GF(q) is constructed such that the coefficient a₀ is the secret and all other coefficients are random elements in the field; the field is known to all participants. Each of the n shares is a pair (x_i, y_i) of numbers satisfying f(x_i) = y_i and x_i > 0. Given any m shares, the polynomial is uniquely determined and hence the secret a₀ can be computed via Lagrange interpolation. However, given m-1 or fewer shares, the secret can be any element in the field.

Shamir’s secret sharing scheme where m = 2 - Diagram from RSA Security Inc.

Shamir’s scheme minimizes the need for random numbers: for every bit in the secret, the dealer must generate t random bits, where t is the threshold number of people.

Notes on Clipperz’s implementation

Coming soon …