Secret Sharing

I found this bibliography on secret sharing useful (over 200 references!). It has not been updated after 1998, but you will find many key work done in this area since it was initially introduced in 1979 independently by Adi Shamir and George Blakley.

The basic idea behind Shamir's (t, n) threshold scheme (t <= n) based on Lagrange interpolating polynomials is to split the secret among n people and you need at least t people to construct the key. (Example: 5 people have formed a business and you don't want to allow access to company bank account if majority does not agree. You define ceiling(5/2) <= t <= 5).

How it works: t points in Cartesian coordinate (x1, y1), ..., (xt, yt) uniquely identifies a polynomial of degree <= t-1 in that space. That the Lagrange polynomial. You define a polynomial f(x) = a0 + a_1.x + .. + a_{t-1}x^{t-1} where a0 represent the secret you want to split among n people. You randomly choose n points that satisfies f(x) and give those to each person. If you have at least t points, you can use the Lagrange polynomial to determine the unique polynomial corresponding to those points. The constant gives you the secret value. In practice, we usually take the modulus of f(x) (i.e. f(x) mod p) to bound the points without revealing no more information than it already reveals. There has been numerous extensions to the above idea in the literature some of which are available in the page I mentioned above.