Tuesday, December 06, 2011

Secret Sharing

Alice has a password to that she can use to open the company safe. She would like to share this with some other co-workers in case she is not available to open the safe. But she doesn't want anyone person to be able to open the safe alone. How can she give her password away while ensuring this?

In 1979 Adi Shamir suggested the following approach to split a secret into n parts to be given to n different parties such that to reconstruct the secret k of them must team up.


Alice has a password to that she can use to open the company safe. She would like to share this with some other co-workers in case she is not available to open the safe. But she doesn't want anyone person to be able to open the safe alone. How can she give her password away while ensuring this?

In 1979 Adi Shamir suggested the following approach to split a secret into n parts (shares) to be given to n different parties such that to reconstruct the secret k of them must team up.

If the secret is denoted by s, the way the it is split into shares is using a polynomial f(x), such that f(0) = s. Each of the n friends i will get the value f(i) as their share.

To ensure that there must be at least k people should get together the degree of the polynomial f must be k-1.

Any team of k users will be able to get together and obtain f(0) = s by first reconstructing the polynomial f using polynomial interpolation.