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.
