This post will present a couple ways to share secrets using polynomials. We have a group of *n* people who want to share a secret between them so that *k* of them will have to cooperate in order to unlock the secret. For example, maybe a committee of *n* = 5 wants to require the cooperation of at least *k* = 3 members.

## Shamir’s method

Adi Shamir came up with the idea of using polynomials to share secrets as follows. First, encode the secret you want to share as an integer *a*_{0}. Next, generate *m* = *k* − 1 other random integers *a*_{1} through *a*_{m} and use these as coefficients of a polynomial *f* of degree *m*:

A trusted party generates *n* random integer values of *x* and gives each person an *x* and the corresponding value of *f*(*x*). Since *m *+ 1 points completely determine an *m*th degree polynomial, if *k* = *m *+ 1 people share their data, they can recover *f*, and thus recover the secret number *a*_{0}. This can be done efficiently, for example, by using Lagrange interpolation. But with fewer than *k* data points, the polynomial remains undetermined.

In practice we’d work over the integer modulo a large prime *p*. While fewer than *k* data points will not let someone completely determine the polynomial *f*, it will narrow down the possible coefficients if we’re working over the integers. Working modulo a large prime instead reveals less information.

## Verifiable secret sharing

There’s a possible problem with Shamir’s method. Maybe the trusted party made a mistake. Or maybe the trusted party was dishonest and shouldn’t have been trusted. How can the parties verify that they have been given valid data without unlocking the secret? Seems we’re at a logical impasse since you’d have to recover the polynomial to know if your points are on the polynomial.

Paul Feldman came up with a way to assure the participants that the secret can be unlocked without giving them the information to unlock it. The trick is to give everyone data that *in principle* would let them determine the polynomial, but in *practice* would not.

We choose a large prime *p* such that *p*-1 has a large prime factor *q* [1]. Then the multiplicative group of non-zero integers mod *p* has a subgroup of order *q*. Let *g* be a generator of that group. The idea is to let everyone verify that

for their given (*x*_{i}, *y*_{i}) by letting them verify that

where all calculations are carried out mod *p*. Our trusted party does this by computing

for each coefficient *a*_{i} and letting everyone know *g* and each of the *A _{i}*‘s.

In principle, anyone could solve for *a*_{0} if they know *A*_{0}. But in practice, provided *q* is large enough, this would not be possible because doing so would require solving the **discrete logarithm problem**, which is computationally difficult. It’s possible to compute discrete logarithms for small *q*, but the difficulty goes up quickly as *q* gets larger.

How do the *A _{i}*‘s let everyone verify that their (

*x*

_{i},

*y*

_{i}) data is correct?

Each person can verify that

using the public data and their personal data, and so they can verify that

## Related posts

[1] Conceptually you pick *p*‘s until you find one so that *p* − 1 has a large prime factor *q*. In practice, you’d do it the other way around: search for large primes *q* until you find one such that, say, 2*q* + 1 is also prime.

Interesting, thanks!

You’ve got a typo and a misformatting in the same sentence:

<>

Everything after the first ‘0’ is subscript, and s/now/know/.

Grrr, lost the quote by using double-angle-brackets: “anyone could solve for a0 if they now A0.”

Thanks for letting me know. Fixed.

There’s a word missing in “This can be efficiently, for example, by using …”.

I share secrets only with my closest polynomials.