Intro to SSS
Before we talk about Proactive Secret Sharing, we probably should briefly talk about Secret Sharing, in particular, we want to focus on Shamir Secret Sharing (SSS).
The idea of SSS is relatively intuitive, a 2-degree polynomial requires 3 points to be exactly located. Likewise, an n-degree polynomial requires n+1 points to be exact. Let’s say for a 2-degree polynomial f(x), we can choose the secret to be the value in f(0) and we send f(1) to Alice, f(2) to Bob, f(3) to Carol, f(4) to Dave, etc.. We can share more points to more people but as long as we have three points, we will be able to recover the value of f(0).
What about PSS?
Ok, now we know what is SSS. What about PSS?
The concept of PSS is to allow key rotation (reshuffle the shares). Let’s say Alice’s computer gets compromised, (1) can Bob/Carol/Dave reshuffle their shares to render Alice’s share obsolete? (2) If Alice later buys a new computer, how can she join the group again?
Of course, we want to do it without the so-called trusted dealer. With a trusted dealer, obviously, Bob/Carol/Dave can send their keys to the dealer, the dealer reconstructs the secret, generate a new polynomial, and distribute new shares to Bob/Carol/Dave. The dealer can also send a new share to Alice when she has a new computer later.
But can we do it without a trusted dealer? Or in other words, can we do it without first reconstructing the secret?
The answer is YES. And it was published back in 1995 by Herzberg at el. at IBM.
Share Reshuffling
To reshuffle the shares, the basic idea is, let’s say, the shares are originally laying on a 2-degree polynomial, for illustration purpose assume it is:
And Bob adds another “random” 2-degree polynomial g(x) with g(0)=0, assuming it is the following
And let f'(x) = f(x) + g(x), since g(0) = 0, therefore f'(0) = f(0), which means the new random polynomial won’t change the secret value.
And note
f'(1) = f(1) + g(1)f'(2) = f(2) + g(2)- and so on.
That means, if Bob distributes g(3) to Carol and g(4) to Dave. Then, they will be able to calculate f'(3) and f'(4) respectively.
With f’(2), f'(3) and f’(4), Bob/Carol/Dave can later reconstruct the secret if they want to (remember f’(0)=f(0)). Therefore, they can then "forget” the values of f(x), and then the valuef(1) remained in Alice’s compromised computer will become useless because f(2), f(3), f(4) no longer exist in the world! What’s even better, no one — including Bob, knows the value of f(0) or f'(0) before and after the reshuffling process.
But although Bob doesn’t know the value of f(0) or f'(0), he is obviously is in a favorable position than Carol and Dave. Therefore, in fact, the algorithm doesn’t just require Bob to generate a random polynomial g(x) and distribute some values to Carol and Dave, likewise, Carol should generate a random polynomial h(x) and distribute some values to other peers, and Dave should generate yet another random polynomial k(x) and distribute some values to peers as well. In this case, everyone is equal and the algorithm is fair to everyone.
To be more explicit, Bob/Carol/Dave should collectively generate a new polynomial f'(x):
f'(x) = f(x) + g(x) + h(x) + k(x)
Where g(x) is a random polynomial generated by Bob, h(x) by Carol, k(x) by Dave, respectively.. And g(0) = h(0) = k(0) = 0
With help from each other, Bob should be able to calculate the new value f'(2) and forget the old value of f(2), Carol should be able to calculate the new value f’(3) and forget the old value of f(3), and likewise, Dave should do the same thing.
But if Bob/Carol/Dave is cheating and tries to corrupt the data during Reshuffling, then it will be a disaster, we can handle that with Verifiable Secret Sharing (VSS), I will talk about it in the future.
Share Recovery
To allow Alice to re-join the group, we want Alice to be able to calculate her own share, but without leaking the secret to her. How can we do that? In fact, we can just reuse the technique we’ve learned in the previous section.
In the previous section, Bob has to generate a random polynomial g(x) with a special requirement that g(0) = 0 , because we don’t want to change the value at x=0. But when recover Alice’s share, we want a random polynomial with x=1 remain the same (because in our example, Alice’s is atx=1), i.e. Bob should generate a random polynomial with g(1) = 0
Therefore, following the concept in the previous section, if Bob/Carol/Dave collectively generate a new f'(x) with
f'(x) = f(x) + g(x) + h(x) + k(x)
Where g(x) is a random polynomial generated by Bob, h(x) is by Carol, and k(x) by Dave, and g(1) = h(1) = k(1) = 0, and then Bob/Carol/Dave calculate their points in f’(x) and share the value in this new polynomial to Alice, Alice will be able to recover her own share, but she will be able to recover the secret, because in this case f'(0) != f(0).
Summary
This is just a high-level overview of how Proactive Secret Sharing works. Obviously there are many implementation details not covered in here. But now you have the basic concept, reading the original paper would be much easier.
In the future, I hope I can write about
- How to increase or decrease the threshold value
- How VSS works
Stay tuned 😀