Homomorphism in Shamir's secret sharing

The homomorphism property in the Shamir's secret sharing scheme is a simple but a very powerful idea that could be useful to reduce the trust we have to put on the dealer to correctly distribute secret shares to users. (See my previous post for an introduction on verifiable secret sharing).

Let's look a simple example to see what this property means.

Assume that we have two degree two polynomials g and f which we can use to create two 3-out-of-n secret sharing schemes where at least 3 out of n users should get together to obtain the secret.

f(x) = 2 + x + x²
g(x) = 3 + 2x + 3x²

We have three users with the following secret shares given from the two secret sharing polynomials where the secrets are 2 and 3 for f and g respectively. Let's call them sub-secrets.

User	f	g
u1	(1,4)	(1,8)
u2	(2,8)	(2,19)
u3	(3,14)	(1,36)

Let's call the combination of the two sub-secrets as the super-secret, which is equal to 5. The problem we have at hand is "how can the users construct the super-secret revealing as little information about the sub-secrets as possible?".

It is not difficult to see that if the three users releases the sum of their secret shares, that is (1, 12), (2, 27) and (3, 50), and do the polynomial interpolation on in it, the combined function gives the super-secret 5. So, the sum of the shares of the secrets are the shares of the sum of the secrets. This is what the homomorphism property is.

The above relationship is defined as the (+, +)-homomorphism. It could be two different operators. For example, Shamir's secret sharing scheme can be converted to (*, +)-homomorphism by using discrete log of secret shares.

References:
Josh Cohen Benaloh, Secret Sharing Homomorphisms: Keeping Shares of a Secret, Proceedings on Advances in cryptology---CRYPTO, 1986