Chapter 4. Secret Sharing

4.1. Two out of Three Musketeers

In Bob's Manhattan living room, three high school chums are confronting a middle-age crisis over scotch and soda. They're all lawyers and disenchanted by the way that money and corruption have ruined the justice system. Inspired by movies like Batman, they decide to recreate The Three Musketeers and prowl about the night looking for people in need of help.

Bob:	Okay. It's settled. We'll file for our license to carry concealed weapons tomorrow. On Friday, we pick out our Glocks.
Harry:	Yes. 9 mm.
Together:	All for one and one for all!
Harry:	You know, I just thought of something. My wife promised her cousin we would go to dinner at her house on Friday. She planned it last month. Could we get the Glocks another day?
Bob:	Sunday's out for me. We're going to my mother's house after church.
Mark:	Well, doesn't fighting evil count for something in the eyes of God?
Bob:	Yes. But I still think we need a contingency. We're not always going to be available. There will be business trips, family visits, emergencies.
Mark:	This is a good point. We might be stuck in traffic or held up in court. We need a plan.
Harry:	Well, what if we said, “All available for one and one for who's there that evening?”
Mark:	Not bad. It's more flexible. But what if just one of us is there?
Harry:	What's the difference?
Mark:	That one person really wouldn't be a group. He would be acting as a vigilante. He could do anything he wanted that evening. Maybe even something that was less than just.
Harry:	So you want a quorum?
Mark:	Yes. I say two out of three of us should be there before someone can start invoking the name of the Three Musketeers.
Bob:	What about costumes? What do we wear if we're alone?
Mark:	Doesn't matter. The most important thing is what we shout as we vanquish the foes. Are we together on this?
Together:	Two out of Three for One and One for Two out of Three!

4.2. Splitting Up Secrets

There are many occasions when you need to split a key or a secret into numerous puzzle parts so that the secret can only be recovered if all of the parts are available. This is a good way to force people to work together. Many nuclear weapons systems, for instance, require two people to turn two different keys simultaneously. Bank safe deposit boxes have two locks and one key is held by the owner while the other is held by the bank.^[1]

¹ It is not clear to me why the bank needs to have its own key on the box. The combination to the vault serves the same purpose.

Splitting information into a number of parts is a good way to make information disappear. Each part may look like noise, but together they create the message. These different parts can take different paths adding further confusion to the entire process.

There are many neat ways to mathematically split a secret into parts. This secret might be the key to an encrypted file or it might be the important factoid itself. The goal is to create n different files or numbers that must all be present to reconstruct the original number. There are also threshold schemes that let you recover the secret if you have some smaller subset of the original parts. If a corporation has five directors, for instance, you might require that three be present to unlock the corporation's secret key used to sign documents.

The mathematics of these schemes is really quite simple and intuitive. Chapter 3 showed how error-correcting codes can be used as primitive secret-sharing devices. That is, you can split up a secret by encoding it with a error-correcting code that can correct wrong bits. (The 7-bit code from page 47 shows how you can split up a secret into seven parts so that it can be recovered if any six parts are available.)

There are numerous problems with this approach. First, some bits are often more privileged than others. In the 7-bit scheme from page 47 in Chapter 3, four of the seven bits hold the original message. The other three are parity bits. If the right four are put together, then the original secret is unveiled. If one of these bits is missing, however, then the parity bits are needed to get the secret.

Second, there can be some redundancy that allows people to unveil the secret even if they don't hold all of the parts. For instance, the 3-bit error-correcting code described on page 40 can recover the correct answer even if one of the three bits is changed. This is because each bit is essentially turned into three copies of itself. If these three copies are split into three parts, then they won't prevent each person from knowing the secret. They have it in their hands. Their part is an exact copy of the whole. This is an extreme example, but the same redundancies can exist in other versions.

A better solution is to use algorithms designed to split up secrets so thatthey can't be recovered unless the correct number of parts is available. Many different algorithms are available to do this, but most of them are geometric in nature. This means that it is often easy to understand them with figures and diagrams.

Deliberately adding errors is one way to prevent this.

4.2.1. Requiring All Parts

Many of the algorithms described later in this section can recover a secret split into n parts if only k parts are available. There are many times when you might want to require that all parts be present. There are good algorithms that work quite well when n = k, but are not flexible to handle cases when k is less than n. These basic algorithms are described here before the other solutions are explained.

One approach is to imitate safe deposit boxes and use n layers of encryption. If f(kⁱ,X) encrypts a message X with key kⁱ, then you can take the secret and encrypt it repeatedly with each of n different keys. That is, compute:

Repeating the same encryption function again and again can introduce some theoretical problems and make analyzing the system tricky.

Each person gets one of the n keys and it should be obvious that the secret can't be recovered unless all of them are present. If one is missing, then the chain is broken and the layers of encryption can't be stripped off.

A simpler approach is to think of the secret as a number, X, and then split it into n parts that all add up to that number, X¹ + X² + X³ + … + Xⁿ = X. If one number is missing, it is impossible to determine what X might be. This solution is an extension of the one-time pad and it is just as secure. If the parts are chosen by a good, secure random number generator, there is no way the people who hold the n − 1 parts can guess what the value of the missing part might be.

In practice, this solution is often computed for each bit in the secret. That is, the secret is split into n parts. If the first bits of the parts are added together, they will reveal the first bit of the secret. If the second bits of the different parts are added together, the result is the second bit of the secret. This addition is done modulo 2, so you're really just determining whether there is an odd or even number of ones in the bits. Here's an example:

X1	= 101010100
X2	= 101011010
X3	= 110010010
X4	= 010101100
X1 + X2 + X3 + X4	= 100110000

If you wanted to split up a secret, then you would generate the first n − 1 parts at random. Then you would compute Xⁿ so that X¹ + … + Xⁿ = X. This is actually easy. Xⁿ = X + X¹ + … + Xⁿ⁻¹.

Are both of these solutions equally secure? The addition method, which is just an extension of the one-time pad, is perfectly secure. There is no way that the system can be broken if you don't have access to all of the parts. There is no additional pattern. The layers of encryption are not necessarily as secure. There are so many variables in the choice of encryption function and the size of the keys, that some choices might be breakable.

Another way of understanding this is to examine the entropy of the equation, X¹ + X² + X³ + … + Xⁿ = X. If each value of Xⁱ has m bits, then there are mn bits of entropy required to determine the equation. If n − 1 values of Xⁱ are recovered, there are still m bits of entropy or 2^m possible solutions to explore.

Intuitively, this encryption equation has the same properties:

If each key, kⁱ, has m bits, then there are still mn bits of entropy in the equation. Unfortunately, the complexity of the function f makes it difficult to provide more mathematical guarantees. If the basic function, f, is secure enough to use for basic encryption, then it should be secure in this case. But, there are many interesting and unanswered questions about what happens if the same system is used to encrypt data over and over again with different keys. ^[2]The simplest approach is the best in this case.

² Some good introduction papers include [CW93].

4.2.2. Letting Parts Slide

Obviously, there are many reasons why you might want to recover some secret if you don't have all of the parts. The most basic algorithms are based on geometry. Imagine that your secret is a number, x. Now, choose an arbitrary value for y and join the two values together so they represent a point on a plane. To split up this secret into two parts, just pick two lines at random that go through the point.- (See Figure 4.1.) The secret can be recovered if the intersection of the two lines is found. If only one line is available, then no knows what the secret might be.

Figure 4.1. A secret, x, is split into two parts by finding two random lines that intersect at (x, y). (y is chosen at random.)

Gus Simmons' chapter on Shared Secrets [Sim93] is a great introduction to the topic.

If there are two lines, then both parts need to be available to find the solution. This technique can be extended so there are n parts, but any two parts are enough to recover the secret.

Simply choose n lines that go through (x, y) at random. Any pair will intersect at (x, y) and allow someone to recover the secret, as in Figure 4.2. When the secret must be split into n parts and any k must be available to recover the secret, then the same approach can be used if the geometry is extended into k dimensions. If k = 3, then planes are used instead of lines. Three planes will intersect only at the point. Two planes will form a line when they intersect. The point (x, y, z) will be somewhere along the line, but it is impossible to determine where it is.

Figure 4.2. A secret, x, is split into n parts by finding n random lines that intersect at (x, y). (y is chosen at random.) Any pair is enough to recover the secret.

Stephan Brands uses this technique in his digital cash scheme [Bra93].

It is also possible to flip this process on its head. Instead of hiding the secret as the intersection point of several lines, you can make the line the secret and distribute points along it. The place where the line meets the y axis might be the secret. Or it could be the slope of the line. In either case, knowing two points along the line will reveal the secret. Figure 4.3 shows this approach.

Figure 4.3. Here the secret is the line itself. Random points along the line are distributed as the parts of the secret. You must have two to recover the line.

Each of these systems offers a pretty basic way to split up a secret key or a file so that some subset of people must be present. It should be easy to see that the geometric systems that hide the secret as the intersection point are as secure as a one-time pad. If you only have one line, then it is impossible to guess where the intersection lies along this line. x = 23 is just as likely as x = 41243. In fact, owning one part gives you no more insight into the secret than owning no part. In either case, all you know is that it is some value of x. This is often called a perfect secret-sharing system.

Some people might be tempted to cut corners and hide information in both the x and the y coordinate of the intersection point. This seems feasible because you can choose any set of lines that goes through this point. This changes the parameters of the system substantially. If you own a part of the secret, then you know something about the relationship between x and y. The slope of the line and the y intercept describe exactly how x and y change in unison.

Roger Dingledine, David Molnar, and Michael J. Freedman designed Free Haven to split up a document among a number of servers using Michael Rabin's secret sharing and information dispersal algorithm. The system also offers a mechanism for paying server owners. [DF00, Rab89a, Rab89b]

In some cases, this might be enough to crack the system. For instance, imagine you are protecting the number of men and women escaping from England on the Mayflower. Storing the number of men in the x coordinate and the number of women in the y coordinate is a mistake. An English spy might know that the number of men and the number of women are likely to be roughly equal given the percentages of men and women in society. This extra information could be combined with one part to reveal a very good approximations of x and y.^[3]

³ You should also avoid storing them as separate secrets broken into parts. In this case, one part from each of the two secrets would still yield enough information. The best solution is to encrypt the two values and split the key to this file.

4.2.3. A More Efficient Method

The basic secret-sharing methods split up a secret, X, into n equal sized parts. If the secret is m bits long, then the parts are also m bits long. This has the advantage of perfect security. If one part is missing, the secret can only be recovered by testing all potential m bits of the missing part—and only if there's a way to check these 2^m possibilities and verify the correct one.

If m bits are too unwieldy for some reason, another quick solution is to encrypt X with some function and split the result into n parts. That is, take the m bits from f(X) and distribute

bits to each part holder.

Hugo Krawczyk offers a scheme that provides more computational assurances that the secret can't be reconstructed without all parts. [Kra94]

This approach sacrifices security for efficiency. Replacing a lost part just requires testing all possible combinations of

bits instead of m bits– a solution that only works if there's a way to test the secret. But if this proposition is difficult enough, then the approach may be useful.

It should be noted that such a function f must be designed so that any change to one bit in the input has the potential to change any output bit. This feature is common if m is smaller than the block of a modern, well-designed algorithm like DES or Rijndael. If m is larger,

should arrange for every every bit to affect every other if X^r stands for the bits in X arranged in reverse order.

If more strength is desirable, the parts can encrypted in a round robin. Let {p¹,p²,…,pⁿ} be the n parts with

bits in each piece. Instead of giving pⁱ to person i, we can give f(h(pⁱ⁻¹),pⁱ) to person i. This means that we can't recover part i without part i − 1. All parts must be present.

4.2.4. Providing Deniability

The error-correcting codes described in Chapter 3 can also be used to add some deniability.

Each of the secret-sharing schemes described in this chapter offer some mindboggling chances to hide data in the Net. There is no reason why one particular file alone should be enough to reveal the information to anyone who discovers it. Splitting a file into multiple pieces is an ideal way to add complete deniability. Imagine, for instance, that the important data is stored in the least significant bits of some image using the techniques from Chapter 9. You could put the important data in the GIF file you use for your home page background and then place this up on the Web. But this is your home page; and the connection is obvious. Another solution is to find, say, three other GIF images on the Web. Maybe one of them is from the Disney World home page, another is from the White House home page, and the third is from some shady hacker site in Europe. Extract the least significant bits from each of these files. You have no control over these bits, but you can use them to hide ownership of the data by using the first secret-sharing scheme described here. If you add up the values recovered from all four sites, then the final information appears.

Now imagine that the word gets out that the information is hidden in the combination of these four sites. Which one of the four is responsible? Disney World, the White House, the hackers in Europe, or you? It is impossible to use the least-significant bits of each of these images to point the finger at anyone. The hidden information is the sum of the four and any one of the four could have been manipulated to ensure that the final total is the hidden information. Who did it? If you arrange it so that the hidden information is found in the total of 100 possible images, no one will ever have the time to track it down.

The Publius system created by Marc Waldman, Aviel D. Rubin and Lorrie Faith Cranor uses basic secret sharing algorithms to distribute the key to a document. [WRC00] For more, see Section 10.6.

This system is just like the classic book ciphers which used a book as the one-time pad.

Of course, there are still problems with the plan. Imagine that Disney World used a slick, ray-traced image from one of their films like Toy Story. These images often have very smooth surfaces with constant gradients that usually have very predictable least significant bits. This would certainly be a defense against accusations that they manipulated the least significant bits to send out a secret message. The images chosen as the foils should have a very noisy set of least significant bits.

The Chi-Squared Test and other measures of randomness can be found in Don Knuth's [Knu81].

4.3. Building Secret-Sharing Schemes

Secret-sharing schemes are easy to explain geometrically, but adapting them to computers can involve some compromises. The most important problem is that computers really deal only with integers. Lines from real numbered domains are neither efficient nor often practical. For instance, five numbers involved in a typical scheme for hiding a secret as the intersection of two lines. Two numbers describe the slope and y-intercept of one line, two numbers describe the second line, and one number describes the x coordinate of the intersection point. If x is an integer, then it is not possible to choose lines at random that have both integers for their slope and y-intercept. If they are available, there will be a few of them.

You can use floating-point numbers, but they add their own instability. First, you must round off values. This can be a significant problem because both sides must do all rounding-off the same. Second, you might encounter big differences in floating-point math. Two different CPUs can come up with different values for x/y. The answers will be very close, but they might not be the same because the different CPUs could be using slightly different representations of values. Most users of floating-point hardware don't care about these very minor differences because all of their calculations are approximations. But this is a problem with cryptography. Changing one bit of an encryption key is usually enough to ruin decryption—even if only the least significant bits that change.

The best solution is to return to finite collections of integers mod some prime number. Adi Shamir Shamir used this domain to hide secrets by choosing polynomials from this domain [Sha79]. Instead of lines or planes to hide the information, he chose k − 1 degree polynomials, p(x), where the first parameter, p⁰ = p(0), holds the secret. (This is a line when k = 2.) One point on the polynomial goes to each part holder. k parts can be used to reconstruct the polynomial and determine the secret, p(0).

Here are the basic steps:

1. Choose a value of q that is prime and greater than n.
2. Find a random polynomial, p(x), of degree k−1 byselecting k−1 random integers between 0 and q. These will be the coefficients of the polynomial, p¹…p^k−1. p⁰ is the secret to be stored away.

3. 

   is the polynomial.
4. Choose n points, x¹…xⁿ. These should be distinct and nonzero. Compute p(x¹)…p(xⁿ). These are the n parts to be distributed to part holders with the values of xⁱ. Any subset of k are enough to determine p(x) and the secret p⁰.
5. To recover the value of p⁰, use Lagrangian interpolation. That is, you can use the points to estimate the derivatives of the polynomial at a point.

This solution uses only integers. It should be obvious that you need k points to recover the polynomial. The easiest way to see this is to realize that having k − 1 points gives no information about p(0). In fact, for any potential value of p(0) you might guess, there is some p that generates it. You can find this p by taking the k − 1 points and your guess for p(0) and generating the polynomial. So, if there is a one-to-one mapping between these guesses, then the system is perfect. The part holder has no advantage over the outside guesser.

The scheme also offers greater efficiency for cases where k is a reasonably large number. In Section 4.2, the geometrical solution was to create a k-dimensional space and fill it with k − 1 dimensional hyperplanes. Intersecting k hyperplanes was enough to reveal the point. The problem with this solution is that the hyperplanes take up more and more space as k grows larger. I don't mean they consume more abstract space—they just require more space to hold the information that represents them. The Shamir scheme shown here doesn't require more space. Each part is still just a point, (x, y) that lies on the polynomial. This is substantially more efficient.

4.3.1. Making Some More Equal

In each of the schemes described in this chapter, the secrets are split into n parts and each of the n parts has the same equal share of control. Humans, being human, are never satisfied with anything as fair as that—some people will want some parts to be more powerful than others.

The most straightforward way to accomplish this is to give some people more parts. For instance, imagine a scheme where you need six parts to reconstruct the secret. That is, you might have a collection of five-dimensional hyperplanes in a six-dimensional space. Any set of six points is enough to uncover the secret, which for the sake of example will be the launch codes for a nuclear missile. Let's say that it takes two commanders, three sergeants, or six privates to launch a missile. This can be accomplished by giving three parts to the commanders, two parts to the sergeants, and one part to each private.

One problem with this solution is that arbitrary combinations of different ranks can join together. So, one commander, one sergeant, and one private can work together to uncover the secret. This might not be permitted in some cases. For example, the U.S. Congress requires a majority of both the House and the Senate to pass a bill. But the votes from one chamber can't be counted against the other. So even though there are 100 Senators and 435 members of the House, a Senator is not worth 4.35 House members. A bill won't pass just because 99 Senators vote for it and only 10 House Representatives. But this could be the situation if someone naively created a secret-sharing scheme by parceling out parts to both sides of Congress from the same shared secret.

A better solution to prevent this is to first split the secret into two equal parts, X^H and X^S, so that both are required to endorse a bill with the digital signature of Congress. Then H^R would be split into 435 parts so that 218 are enough to recover it. H^S is split into 100 parts so that 51 are enough to recover it.

Numerous combinations can make these schemes possible. Practically any scheme can be implemented using some combination and layers of secrets. The only problem with very complicated systems is that they can require many different dimensions. For instance, if you want a system that takes 17 privates, 13 sergeants, or 5 generals to launch some missiles, then you can use a system with 17 × 13 × 5 dimensions. This can get a bit arcane, but the mathematics is possible.

4.4. Public-Key Secret Sharing

All of the algorithms in this section share one set of bits, the secret. This secret may be used for anything, but it is probably going to be used as a key to unscramble some information encrypted with a secret-key algorithm. The notion of splitting up authority and responsibility can also be incorporated into public-key algorithms. In these schemes, the actions for scrambling and unscrambling can be split and controlled separately. The holder of one key controls encryption and the holder of the other key controls decryption. If secret sharing is combined with public-key encryption, one group must agree to encrypt a message and another group must agree to decrypt it.

Approaches like this are often called threshold decryption or threshold signatures.

One easy solution is to combine any public-key algorithm with any of the secret sharing solutions. The keys are just collections of bits and these collections can be split into arbitrary subcollections using any basic secret splitting solution. This mechanism is perfectly useful, but it has limitations. If a group of people get together to encrypt or decrypt a message, the key must be put together completely. Once it is assembled, whoever put it together now controls it. The secret sharing feature is gone.

This approach splits the ability to decrypt a public key message among a group of k people. Anyone can send a message to the group, but they all must agree to decrypt it. No information obtained from decrypting one message can be used to decrypt the next. The system relies on the strength of the discrete log problem. That is, it assumes that given g,p, and g^x mod p, it is hard to find x.

Similar techniques can be used to produce anonymous digital cash and secure voting solutions. [Bra95b, Bra95a]

The private key consists of k values {x¹,…,x^k} that are distributed among the k members who will have control over the decryption process. The public key is the value,

mod p, where the values of gⁱ and p are publicly available numbers. The values of gⁱ may be generators of the group defined modulo p but the algorithm will work with most random values less than p.

A message to the group is encrypted by choosing a random value, y, and computing

mod p,

mod p,…

mod p. Then the value a^y mod p is computed and used to generate a secret key for encryption the message with an algorithm like AES. The message consists of this encrypted data and the k values g^y1mod p, g^y2mod p,… g^yk mod p. This mechanism, first proposed by Taher Elgamal, is very similar in spirit to Diffie-Hellman key exchange.

The message can be decrypted by distributing the k values to the group. Each person computes

mod p and returns this value to the group leader who multiplies them together.

mod p.

The same set of keys can also generate digital signatures for the group with a modified version of the digital signatures used with the Diffie-Hellman-style public key system. Here are the steps:

1. The signers and the signature verifier agree on a challenge value, c. This is usually generated by hashing the document being signed. It could also be created by the verifier on the fly as a true challenge.
2. Each member of the group chooses a random witness, wⁱ and computes g^wii mod p.
3. Each member of the group computes rⁱ = cxⁱ + wⁱ and g^rii mod p.
4. The group discards the values of wⁱ and gathers together the rest of the values in a big collection to serve as the signature. These values are: {r¹ = cx¹ + w¹,…r^k = cx^k + w^k},

   

   , and the product of:

   

5. Anyone who wants to check the signature can compute

   

   mod p and make sure it is the same as the product of

   

   .

Similar solutions can be found using RSA-style encryption systems. In fact, some of the more sophisticated versions allows RSA keys to be created without either side knowing the factorization. [BF97, GRJK00, BBWBG98, CM98, WS99, FMY98]

4.5. Steganographic File Systems and Secret Sharing

Secret sharing algorithms split information into a number of parts so that the information can only be recovered if some or perhaps all of the parts are available. The same basic algebra can also be used by one person to hide their data so only the person who knows the right combination of parts can verify that the data is there. This application may be valuable if you happen to be storing the information on your hard disk and you want to deny that it is there.

Ross Anderson, Roger Needham, and Adi Shamir created two versions of what they called a steganographic file system. [ANS98] Their first uses math very similar to secret sharing and so it is described here.

The system grabs a large block of disk space, randomizes it, and then absorbs files that are protected with passwords. If you don't know the password, then you can't find the file. If you do know the password, then the random bits produce the file. There's no way to identify that the file exists without the password.

“Three may keep a secret if two are dead.”—Benjamin Franklin

This scheme is far from perfect. For it to work well, the passwords must be assigned in a hierarchy. That means if someone knows one password, Kⁱ, then they must know all other passwords K^j where 0 ≤ j < i. If there are only three files, then the person with access to file 3 must also have access to files 1 and 3. Anderson, Needham and Shamir imagine that a person under interrogation may reveal the password to several modestly dangerous files without revealing the more sensitive ones.

The mathematics is all linear algebra. For the sake of simplicity, the system is defined for binary numbers where addition is the XOR (⊕) operation and multiplication is the AND (·) operation.

A basic steganographic file system can hold m files that are n bits long. In the beginning, the files are set to be random values that are changed as information is stored in the system. It often helps to think of the file system as a big matrix with m rows and n columns. Let Cⁱ stand for the i^th row.

The password for file j is K^j, a m-bit-long vector where K^j(i) stands the i^th bit of the vector. To recover file j from the file system, add together all of the rows, Cⁱ, where K^j(i) = 1. That is:

How do you store a file in the system? Here's a basic sketch of the steps for storing one file:

1. Break it into n bit blocks.
2. Choose a password for each block. One good solution is to concatenate a random string, S, before the password, hash it with a cryptographically secure hash function, H, and take the first m − 1 bits to serve as K^j.
3. Add a parity bit to K^j to make sure it is the correct length. Use odd parity to ensure that the number of 1 bits in the vector is odd. That is, set the last bit to be one if there are an even number of ones in the first m − 1 bits and a zero if there are an odd number.
4. Encrypt the block with a separate encryption function, ideally using a different key constructed by appending a different random string. This encryption function is necessary because of the linear nature of the file system. If an attacker can establish some part of the file, D, then the attacker can solve some linear equations to recover K^j. If the files aren't encrypted, an attacker can extract the file if the attacker can guess a phrase and its location in the file.
5. Replace Cⁱ with D ⊕ Cⁱ for all i where K^j(i) = 1.

This basic algorithm will store one file in the system. If it is used repeatedly, it may bring problems because new files can overwrite other files. If you want to store more than one file in the system, you need to ensure that they will not disrupt each other.

The simplest solution is to choose the m values of K^j so that they're orthogonal vectors. That is, Kⁱ · K^j = 1 if and only if i = j. In all other cases, Kⁱ · K^j = 0. If the password vectors are orthogonal, then m different files can be stored in the system without disturbing each other.

In other words, whenever the values of D are added to different rows C^j, that it will not distort another file. Why? If K^p · K^q = 0, then there are only an even number of bits that are one in both K^p and K^q. Imagine that you're replacing C^j with D⊕C^j for all j where K^p(j) = 1. Some of these rows will also rows which are storing parts of another file defined by key K^q. Why isn't this file disturbed? Because D will only be added to an even number of rows and the value will cancel out. D ⊕ D = 0.

Consider this example with K:

0	1	1	1	0
1	0	1	1	0
0	0	1	1	1
1	1	1	0	1
1	1	0	1	1

This matrix contains the keys for 5 files. The first row, for instance, specifies that the first file consists of C² ⊕ C³ ⊕ C⁴. The second row specifies that the second file consists of C¹ ⊕ C³ ⊕ C⁴. If new data is stored in the first file, then C², C³, and C⁴ will all become C² ⊕ D, C³ ⊕ D, and C⁴ ⊕ D respectively. What does this do to the second file? C¹ ⊕ C³ ⊕ C⁴ becomes C¹ ⊕ (C³ ⊕ D) ⊕ (C⁴ ⊕ D) = C¹ ⊕ C³ ⊕ C⁴ ⊕ D ⊕ D = C¹ ⊕ C³ ⊕ C⁴.

Here's a basic algorithm for constructing K from a list of m passwords, P¹,P²,…P^m. Repeat this for each password, Pⁱ.

1. Let Kⁱ = H(Pⁱ), where H is some cryptographically secure hash function.
2. For all j < i, let Kⁱ = (Kⁱ · K^j)K^j ⊕ Kⁱ. This orthonormalization step removes the part of the previous vectors that overlaps with the new row. That is, it ensures that there will only be an even number of bits that are one in both rows. It does this for all previous values.
3. If Kⁱ = 0, then an error has occurred. The new chosen key is not independent of the previous keys. Set Kⁱ = H(H(Pⁱ)) and try again. Continue to hash the password until an acceptable value of Kⁱ is found that is orthonormal to the previous keys.

This algorithm does not compute the values of Kⁱ independently of each other. You must know the values of all K^j where j < i to compute Kⁱ. This is less than ideal, but it is unavoidable at this time. Anderson, Needham and Shamir decided to turn this restriction into a feature by casting it as a linear file access hierarchy. If you can read file i, then you can read all files j where j < i.

Forcing all of the keys into a hierarchical order may not always be desirable. Another technique for finding keys is to restrict each person to a particular subspace. That is, split the keyspace into orthogonal parts. If person i wants to choose a particular Kⁱ, then that person must check to see that Kⁱ is in the right subspace.

The easiest way to split the keys into orthogonal subspaces is to force certain bits in the key to be zero. Alice might use keys where only the first ten bits can be set to 1, Bob might use keys where only the second ten bits can be non-zero, and so on.

If necessary, Alice, Bob and the rest of the gang can agree on a random rotation matrix, R, and use it to rotate the subspaces. So Alice will only choose a key vector if RKⁱ has zeros in all the right places.

This version of the file system is also a bit unwieldy. If you want to read or write a file D, then you may need to access as many as m other rows. This factor can be substantial if m grows large. This can be reduced by using non-binary values instead of bits for the individual elements of Kⁱ.

4.6. Summary

Secret-sharing is an ideal method for distributing documents across the network so no one can find them. It is an ideal way for people to deny responsibility. In some cases, the parts of the secret can be from the Web pages of people who have nothing to do with the matter at hand.

• The Disguise Secret sharing lets you share the blame.
• How Secure Is It? The algorithms here are unconditionally secure against attacks from people who have less than the necessary threshold of parts.
• How to Use It. The XOR algorithm described here is easy to implement. It is an ideal way to split up information so that every party needs to be present to put the information back together.