0:38

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.

1:28

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.

4:25

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.

9:35

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,