Recover from compromised shares with Shamir Secret Sharing

Question

He is a quote from Wikipedia page for Secret Sharing:

If the players store their shares on insecure computer servers, an attacker could crack in and steal the shares. If it is not practical to change the secret, the uncompromised (Shamir-style) shares can be renewed. The dealer generates a new random polynomial with constant term zero and calculates for each remaining player a new ordered pair, where the x-coordinates of the old and new pairs are the same. Each player then adds the old and new y-coordinates to each other and keeps the result as the new y-coordinate of the secret.

The idea here is that if you add a polynomial with constant term $0$ to another polynominal, it doesn't change the constant term. But I don't get how this is better than just redistributing new shares.

If you distribute the updates over an insecure channel, then the attacker can intercept them, steal new shares and convert them to old shares by substracting the update. So you have to distribute the updates over a channel as secure as the one originally used to distribute shares. So what's the point of using updates instead of just generating new shares?

Answer 1

The point is that the dealer generating the update needn't know what the shared secret is.

If we had a dealer that remembered what the shared secret was (or we asked enough people to contribute their shares so that the dealer could reconstruct it), then yes, the dealer could generate new shares.

However, this would require is a dealer that did know the secret. In contrast, anyone can generate a random polynomial with an constant term $0$; all they would need is the degree of the polynomial (that is, the threshold of the secret sharing scheme), the field the polynomial is in, and the $x$ coordinates of the uncompromised parties; all this can be made public without compromising the security of the system.

Remember, the whole point of the shared secret scheme was that no one knows what the secret is (until it's officially time to reconstruct it).

Answer 2

Some additional points on poncho's excellent answer:

If the attacker can eventually steal all shares ever distributed, then nothing can provide secrecy. So we have to assume some constraint on how many shares can be compromised, or the rate of compromise.

The solution outlined in the article has the property that, once new shares are distributed (and none have been comprised yet), the adversary is back at "square one:" it's as if the system was started from scratch, and he never compromised anyone in the first place. This assumes that the original shares were securely erased, so that further corruptions only reveal the new (combined) shares, not the original ones.

More generally, this refreshing property is at the heart of what is known as "proactive security," which provides security even if the total number of compromises exceeds the threshold of the scheme, as long as refreshes (and erasures) are frequent enough that there aren't too many compromises between refreshes.