Shamir's Secret Sharing - Shamir's Secret-sharing Scheme

Shamir's Secret-sharing Scheme

The essential idea of Adi Shamir's threshold scheme is that 2 points are sufficient to define a line, 3 points are sufficient to define a parabola, 4 points to define a cubic curve and so forth. That is, it takes points to define a polynomial of degree .

Suppose we want to use a threshold scheme to share our secret, without loss of generality assumed to be an element in a finite field of size where is a prime number.

Choose at random coefficients in, and let . Build the polynomial . Let us construct any points out of it, for instance set to retrieve . Every participant is given a point (a pair of input to the polynomial and output). Given any subset of of these pairs, we can find the coefficients of the polynomial using interpolation and the secret is the constant term .