There are other techniques for message broadcasting, some of which avoid the previous problem. These are discussed in Section 22.7.

3.6 Secret Splitting

Imagine that you’ve invented a new, extra gooey, extra sweet, cream filling or a burger sauce that is even more tasteless than your competitors’. This is important; you have to keep it secret. You could tell only your most trusted employees the exact mixture of ingredients, but what if one of them defects to the competition? There goes the secret, and before long every grease palace on the block will be making burgers with sauce as tasteless as yours.

This calls for secret splitting. There are ways to take a message and divide it up into pieces [551]. Each piece by itself means nothing, but put them together and the message appears. If the message is the recipe and each employee has a piece, then only together can they make the sauce. If any employee resigns with his single piece of the recipe, his information is useless by itself.

The simplest sharing scheme splits a message between two people. Here’s a protocol in which Trent can split a message between Alice and Bob:

(1)  Trent generates a random-bit string, R, the same length as the message, M.

(2)  Trent XORs M with R to generate S.

M ⊕ R = S

(3)  Trent gives R to Alice and S to Bob.

To reconstruct the message, Alice and Bob have only one step to do:

(4)  Alice and Bob XOR their pieces together to reconstruct the message:

R ⊕ S = M

This technique, if done properly, is absolutely secure. Each piece, by itself, is absolutely worthless. Essentially, Trent is encrypting the message with a one-time pad and giving the ciphertext to one person and the pad to the other person. Section 1.5 discusses one-time pads; they have perfect security. No amount of computing power can determine the message from one of the pieces.

It is easy to extend this scheme to more people. To split a message among more than two people, XOR more random-bit strings into the mixture. In this example, Trent divides up a message into four pieces:

(1)  Trent generates three random-bit strings, R, S, and T, the same length as the message, M.

(2)  Trent XORs M with the three strings to generate U:

M ⊕ R ⊕ S ⊕ T = U

(3)  Trent gives R to Alice, S to Bob, T to Carol, and U to Dave.

Alice, Bob, Carol, and Dave, working together, can reconstruct the message:

(4)  Alice, Bob, Carol, and Dave get together and compute:

R ⊕ S ⊕ T ⊕ U = M

This is an adjudicated protocol. Trent has absolute power and can do whatever he wants. He can hand out gibberish and claim that it is a valid piece of the secret; no one will know it until they try to reconstruct the secret. He can hand out a piece to Alice, Bob, Carol, and Dave, and later tell everyone that only Alice, Carol, and Dave are needed to reconstruct the secret, and then fire Bob. But since this is Trent’s secret to divide up, this isn’t a problem.

However, this protocol has a problem: If any of the pieces gets lost and Trent isn’t around, so does the message. If Carol, who has a piece of the sauce recipe, goes to work for the competition and takes her piece with her, the rest of them are out of luck. She can’t reproduce the recipe, but neither can Alice, Bob, and Dave working together. Her piece is as critical to the message as every other piece combined. All Alice, Bob, or Dave know is the length of the message—nothing more. This is true because R, S, T, U, and M all have the same length; seeing anyone of them gives the length of M. Remember, M isn’t being split in the normal sense of the word; it is being XORed with random values.

3.7 Secret Sharing

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 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 allow a launch.

This is easy to solve. Make a mechanical launch controller. Give each of the five officers a key and require that at least three officers stick their keys in the proper slots before you’ll allow them to blow up whomever we’re blowing up this week. (If you’re really worried, make the slots far apart and require the officers to insert the keys simultaneously—you wouldn’t want an officer who steals two keys to be able to vaporize Toledo.)

We can get even more complicated. Maybe the general and two colonels are authorized to launch the missile, but if the general is busy playing golf then five colonels are required to initiate a launch. Make the launch controller so that it requires five keys. Give the general three keys and the colonels one each. The general together with any two colonels can launch the missile; so can the five colonels. However, a general and one colonel cannot; neither can four colonels.

A more complicated sharing scheme, called a threshold scheme, can do all of this and more—mathematically. At its simplest level, you can take any message (a secret recipe, launch codes, your laundry list, etc.) and divide it into n pieces, called shadows or shares, such that any m of them can be used to reconstruct the message. More precisely, this is called an (m,n)-threshold scheme.

With a (3,4)-threshold scheme, Trent can divide his secret sauce recipe among Alice, Bob, Carol, and Dave, such that any three of them can put their shadows together and reconstruct the message. If Carol is on vacation, Alice, Bob, and Dave can do it. If Bob gets run over by a bus, Alice, Carol, and Dave can do it. However, if Bob gets run over by a bus while Carol is on vacation, Alice and Dave can’t reconstruct the message by themselves.