Friday, February 18, 2011

A simple construction of a veribable secret sharing scheme

In a SS (Secret Sharing) scheme a secret is split among many people and some of them need to corporate to build the secret from their shares of the secret. In in it is basic form, a dealer who possesses the secret s splits the secret and gives the secret share si to each party Pi, i = 1, 2, ..., n. The protocol makes sure that there should be at least t+1 parties to derive the master secret s. In other words, t or less number of parties cannot derive the secret.

In a normal SS scheme, the dealer is assumed to be honest. What if the dealer can be malicious? That's where VSS (Verifiable Secret Sharing) comes to play. VSS is similar to SS except that it allows each party to verify that the share given to them, si, is a valid one.

Here's a simple VSS scheme using Shamir's secret sharing and additive homomorphic encryption.

An additive homomorphic encryption scheme (e.g. ElGamal cryptosystem) allows us to perform addition over encrypted data. In particular, we use the following properties. Let E be the encryption algorithm and m1, m2 two numbers.

E(m1)E(m2) = E(m1 + m2)
E(m1)m2 = E(m1m2)

The dealer generates secret shares just like in the Shamir's SS scheme. For (n, t+1) (i.e. out of n parties, there should be at least t + 1 parties to construct the secret, the dealer selects a random degree t polynomial f with f(0) = s:

f(x) = s + a1x + a2x2 + ... + atxt

The dealer sends the secret share (i, f(i)) (f(i) = si) to each party Pi through a private communication channel. Now t + 1 parties can perform a polynomial interpolation and obtain a unique polynomial which is equal to f and get the secret f(o).

In order to verify their secret shares, the dealer distribute an additional piece of information. The dealer generates public and private key pair for the additive homomorphic encryption E and broadcasts the encrypted coefficients of f, that is, E(s), E(a1), E(a2), ..., E(at). A party Pi, first encrypts it share and compare if the following holds. If it is true, it concludes that the dealer has given a valid secret share.

E(si) ==? E(s)E(a1)iE(a2)i2 ... E(at)it

How to Share a Secret, 1979, Adi Shamir
A Practical Scheme for Non-interactive Verifiable Secret Sharing, 1987, Paul Feldman

1 comment:

kun said...

I think the equation:
E(si) ==? E(s)E(a1)iE(a2)i2 ... E(at)it

cannot meet?
can you give me an detail explanation about that?
thank you