Sharing Secrets Among Friends

Using Polynomials

It is easy to extend this scheme to more people. To split a message among more than two people, just XOR more random bit strings into the mixture so all the parts XORed together reproduce the message. For example, 10011011, 11101001, and 01110010, XOR to form the message 00000000.

The only problem with this splitting scheme is that if any of the pieces gets lost, so does the message. So, if an employee with a piece of your sauce recipe quits without leaving the piece of the puzzle behind, you're out of business. The recipe can't be reproduced, but you can't use it either. This piece is as critical to the message as every other piece in the message combined.

A more complicated sharing scheme can fix that problem. Let's say you're setting up a launch program for a nuclear missile. You want to make sure that no single raving lunatic can initiate a launch. You also want to make sure that no two raving lunatics can initiate a launch. You want at least three out of five officers to be raving lunatics before you will allow a launch. Give each of the five officers a key and require three keys to blow up whoever is being blown up these days. Physical keys make it easy, but you can do the same thing mathematically.

Make the launch message the linear term of an otherwise random quadratic polynomial. That is, if the message is m, invent some polynomial of the form ax² + bx + m. Give each officer the solution of the polynomial evaluated at a different x. If the polynomial were written as 49x² - 28x + 72, Officer Smith might get the result at x = 21, Officer Jones might get the result at x = -2, Officer McDonald might get the result at x = 11, and so on. None of the officers would know the polynomial; they would just know that it was of the form ax² + bx + m. Since the quadratic polynomial has three unknowns, any three officers can throw their pieces into a linear algebra program and solve for m. Two officers cannot. One officer cannot. Four or five officers are redundant.

This sharing scheme can be easily generalized. If you want to divide the message into 30 equal parts so any six people can get together and reproduce the message, give each of the 30 people the evaluation of a polynomial of degree five (ax⁶ + bx⁵ + cx⁴ + dx³ + ex² + fx + m). Six people can solve for the six unknowns; five people can't do a thing.