Proactive Secret Share for Eigen Secret Recovery
PDF click here
Big news from Coinbase that it acquired leading cryptographic security company Unbound Security with $1500M. Unbound is famous for his MPC based key management solution. Here we introduce how it’s secret share works.
Shamir’s Secret Sharing(SSS)
For basic Secret Share Schema, namely Shamir’s Secret Sharing, formulated by Adi Shamir, is one of the first secret sharing schemes in cryptography. It is based on polynomial interpolation over finite fields. Shamir’s Secret Sharing is an ideal and perfect (k, n)-threshold scheme, in which the secret is splited into n shares, but with at least k shares to recover the secret.
How does it work? We need some polynomial knowledge. For instance, 2 points are sufficient to define a line, 3 points are sufficient to define a parabola, 4 points to define a cubic curve and so forth.
From there we can see that for each polynomial
where the degree is k, that’s say we at most have k roots in finite fields. For $$k = 1, x = -a_0$$ , for k = 2, the roots would be
where if there are 2 roots. On the other side, Let us consider if we have k-1 roots $$x_i, i∈in[0,k-1]$$, we can easily restore the polynomial by interpolation, and the a₀ can be calculated by :
The SSS utilizes the f(0) to represent the secret, and then calculates n values, (i, f(i)) as the shares for each players.
For instance, let f(x) = 3x + 4, the secret is 4, and we let Alice keeps (1, 7), and let Bob keeps (2, 10). When we try to restore the secret, we just calculate
, which is the secret.
This seems very safe for we to store and restore the secret without centralized party. But There is still a very headache issue, if the quorum of the players are compromised by the attackers, the secret will be leaked. So we need to refresh the shares periodically, now the proactive secret share come into our eyes.
Proactive Secret Share Scheme(PSS)
For the share holders, Alice, Bob, Carol and Dave. If Dave was compromised at sometime point but that is still not known to others, then the hacker will try to compromised more players, until it convinces the quorum to reveal the secret. So the idea to fix this is refresh the shares and kick out the vulnerable players.
We can observe that if we modify the coefficient $$x_i, i\in[1,k-1]$$, we get total different polynomial, but keep f(0), the secret the same. This also changed the shares each player holds. So we can simply add a new polynomial g(x) to f(x), while g(0) = 0. So the problem can be transformed to how we negotiate the g(x) safely and consistently among all players.
Multiparty computation (MPC) saved the day. MPC protocols allow multiple parties to calculate a function together while keeps the input of each party private to the others. The most well-known example is the Yao’s Millionaires’ problem, that is two millionaires try to figure out who is richer but does not tell the how much money it owns to each other.
The intuitional idea is the player i generates a new polynomial $$Z_i(x)$$ with $$Z_i(0)=0$$ and roots are $$x_i, i ∈[0, k]$$, then calculate $$Z_i(x_j)$$, and shares it to player j. So player i shares only one point $$(j, Z_i(x_j))$$ to player j, and no one else know the whole coefficient of $$Z_i(x)$$.
At the end of refresh interval, player I has the new share:
while keeping $$N(0) = f(0) = secret$$. And the new polynomial is
And All of the non-updated shares the attacker accumulated become useless, since the honest party deleted their old shares after the updating.
The last question is how the players know the root $$x_i$$ in advance, It can be solved by simply setting $$x_i$$ to the number i. More details can be found in this video.
Now, we have simply explain how the PSS work. And In summary, Proactive secret sharing (PSS) schemes are designed for settings where long-term confidentiality of secrets has to be guaranteed.