*s*splits the secret and gives the secret share

*s*to each party P

_{i}_{i},

*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,

*s*, is a valid one.

_{i}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

*m*two numbers.

_{1}, m_{2}*E(m*

_{1})E(m_{2}) = E(m_{1}+ m_{2})*E(m*

_{1})^{m2}= E(m_{1}m_{2})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 + a*

_{1}x + a_{2}x^{2}+ ... + a_{t}x^{t}The dealer sends the secret share (

*i, f(i)*) (

*f(i) = s*) to each party P

_{i}_{i}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(a*. A party P

_{1}), E(a_{2}), ..., E(a_{t})_{i}, 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(s*References:

_{i}) ==? E(s)E(a_{1})^{i}E(a_{2})^{i2}... E(a_{t})^{it}How to Share a Secret, 1979, Adi Shamir

A Practical Scheme for Non-interactive Verifiable Secret Sharing, 1987, Paul Feldman

## 1 comment:

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

Post a Comment