In segment 4.3, we'll talk about how to share and split keys. Up to now, we've talked about different ways of storing and managing the secret keys that control BitCoins, but we've always put a key in a single place. Whether that's locked in a safe, or in software, or on paper, it's in one place. And storing the key in one place leaves us with a single point of failure. So that if something goes wrong with that single storage place, then we're in trouble. So here, what we'd like to do now is be able to take a key and split it up into pieces and share those pieces around so that we avoid the single point of failure problem. And so we're gonna introduce a cryptographic trick called Secret sharing. The idea is we're gonna take some secret, in our case, a secret key, and we're gonna divide it up into some number N of pieces. And we're gonna do that in such a way that, if we're given any K of those pieces, then we'll be able to reconstruct the original secret. But if we're given fewer than K pieces, then we won't be able to learn anything about the original secret. So for example, we might have N=2 and K=2. That means we're dividing the secret into two pieces, and you need both pieces to put them together. And a specific way of getting N=2, K=2 Secret sharing like this is as illustrated here. That first we're going to generate a number P which is a large prime number. Doesn't need to be secret or anything, just really big. S is gonna be the secret and the secret has to be between 0 and P minus one inclusive. And then we're gonna generate a random value R, secretly, which is also within the range between zero and P minus one. And now we're gonna split our secret into two pieces, X1 and X2. Piece X1 is gonna be (S+R) mod P and remember that modulo is the operation that's sometimes written with the percent sign in programming languages. It just means, take this value S+R, and divide it by P, and keep the remainder, when we do that division. That's S+R mod P. So that'll be X1, our first share and the other share, X2, is gonna be S+2R mod P. Okay, and now if we have both of these shares X1 and X2 we can combine them to reconstruct the secret S. What we do is we compute two times X1 minus X2 mod P. So two times X1 is 2S plus 2R and X2 which we're subtracting off is S plus 2R. And so we have 2S minus S, that leaves us with an S. We have 2R minus 2R, and so the 2Rs cancel out, and we're left with just S mod P, which is equal to S because S is less than P. And so we can reconstruct the secret in this way. So given two shares we can reconstruct but given only one of the shares, it turns out we don't learn anything. And to see why that is, consider X1 we took S which is the secret, but we added to it a random number which could take on any value between zero and P minus 1 with equal likelihood. And if you think about it, you can convince yourself that the result of S plus R modulo P is equally likely to take on any value between zero and P minus 1, and that's true regardless of what S was. And so this share by itself just looks like a purely random number and doesn't convey anything about what the value of S might have been. Similarly this share by itself is also equally likely to take on any value between zero and P minus one. And therefore doesn't convey any information about S. So that's N=2, K=2. Given both shares, we can get back the secret given one share, we can't. Okay, now in general we can talk about how to get higher values of N and K. For example, let's talk about how to get higher values of N, where K equals two. That is, we're going to want to require two shares to be put together to reconstruct the secret, but we're gonna make more than two shares that are eligible for use in this way. And so the way we'll do that is to draw our x standard, x and y axis here. And we're gonna add a point here at (0, S), where S is the secret. And so obviously if somebody can learn what this point is, then they will have reconstructed the secret. Okay, now we're gonna draw a line and we're gonna draw a line that has a random slope R. R is gonna be generated randomly and so we get a line like this. And now, we can give out shares. The first share is this point here at x=1 and y is S+R. The second share is here at, x=2 and y turns out to be S+2R. The third share is here, x=3, and y is S+3R and so on. We can go as far up this line as we want, and generate as many shares as we want. Okay, now if you think about it, you can convince yourself that given any two points you can interpolate and find S, right? That's a property of a line. Given any two points on a line, you can interpolate the line. Imagine setting down a ruler that exactly touches say these two points, and then you can draw a straight line along that ruler. So given any two points we can reconstruct what this line is. You can see where the line crosses the Y axis, that would be 0,S and that would give you back the secret. But given just one point you don't really know anything. Because if you have, say, this point well the line might be sloped like this, but equally likely it might be sloped like this, it could be sloped any way at all. And so given just this point, you don't really know anything about where this line might cross the y axis, so you don't know anything about S. And in fact, you can prove that if you do this arithmetic, modulo large prime P, like we did before in the previous slide. Then in fact, you can prove that any two points are sufficient to interpolate and find S and fewer than two points don't tell you anything about S. And so this gives us N equals any value, and K=2. All right, but now what if we wanted to require more than two points? Well for two points we drew a line because any two points are sufficient to uniquely specify a line. If we wanna require three points, what we're going to do is use a quadratic function. Because any three points are sufficient to reconstruct a quadratic function. And so, we can use this table to understand what's going on. So, if use the equation S+RX mod P with the random parameter R. That's the slope that we saw in the previous slide. Then you need two points to recover S because you need two points to interpolate a line. If on the other hand, if then you use a quadratic, that is S plus some random value R1 times X, plus some other random value R2 times X squared. Then there are two random parameters, R1 and R2, and with any three points you can uniquely interpolate a quadratic, and get back S. And we can just go up the ladder here, if we use a cubic function. There are three random parameters, we need four points. And in any case you can generate as many points as you want on the line or the quadratic or the cubic. And therefore you can get any value of N. And you see how you can get any value of K by just going to higher and higher order polynomials. And so this scheme will let you take any secret and split it onto N shares, such that K shares or more are needed to reconstruct. And that turns out to be a really useful thing, because now you can take a secret key or other secret information, and split it up in this way. Support K-out-of-N splitting, for any K and N. So let's talk about the good and bad that we get out of this process. The good part is that we can store the shares separately, and the adversary needs to be able to recover K shares in order to get back what the secret was. And that's the good news, right? That means that if we use, say, K equals three, N equals four, the adversary needs to get break into three separate places. And if we're clever about storing those separate shares in places that are far apart and independently secured, then we could make the adversary's job much more difficult. And indeed, if we've noticed that the adversary is compromised one of those places, we can then raise out and try to recover the other shares and address the problem. The other thing that's good about this, is that we can afford to lose some of the shares. If we do three out of four secret splitting, then we can lose one share and we'll still have three left. And so we can put those three remaining ones together and still get back the key. So even though we are spreading out the information, there are more places where information might be lost. We can also tolerate the loss of some of those. In general we can tolerate the loss of N-K of them. Now that's the good news. The bad news is that if we take a key and we split it up in this way, and we then wanna go back and use the key to sign something, we still need to bring the shares together and recalculate the initial secret in order to be able to sign with that key. And that point where we bring all the shares together and recombine them is still a single point of vulnerability. Where an adversary might be able to attack us, and that's the bad news. So although this is useful it's not a panacea and there's something else that we like which is the ability to generate separate shares, and use those shares separately in order to sign. And that's what's behind the concept of Multi-sig that we saw earlier in Lecture 3. So, if you recall Multi-sig in Lecture 3, it lets you keep the shares or the different pieces that need to sign a particular transaction apart and to allow them to approve the transaction separately without needing to reassemble the key at any point. So just as an example of application of that, suppose that Andrew, Arvind, Ed, and Joseph are co-workers. Let's say they're cofounders of a company and the company has a lot of bitcoins. Hey, you know, we can dream. Now, what we might want to do is use multi-sig to protect our large store of BitCoins. So what we're going to do is have each of the four of us generate a key pair, and we're going to for, our company's cold storage, store the coins so that we require multi-sig, with three out of the four keys signing. Now the result of that is that we know that we're relatively secure if the four of us keep our keys separately and secure them differently. But someone would have to compromise three out of the four keys that, if some employee or even two employees go rogue, those rogue employees can't steal all of the company's coins, because you would need a conspiracy of three out of four to do that. And we also know that if something goes wrong, if one of us loses our key, or if one of us gets run over by a bus and our brain wallet is lost, the others can still get the coins back and transfer them over to a new place. And so multi-sig allows you, or helps you, to manage large bodies of cold-stored coins in a way that's relatively secure and that requires action by multiple people before anything drastic happens.
