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 methodAdi 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 a0.
Next, generate m = k-1 other random integers a1 through am and use these as coefficients of a polynomial f of degree m:A trusted party generates n random integers values of x and gives each person an x and the corresponding value of f(x).
Since m+1 points completely determine a mth degree polynomial, if k = m+1 people share their data, they can recover f, and thus recover the secret number a0.
This can be 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 sharingThere’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 thatfor their given (xi, yi) by letting them verify thatwhere all calculations are carried out mod p.
Our trusted party does this by computingfor each coefficient a1 through am and letting everyone know g and each of the Ai‘s.
In principle, this reveals enough information to solve for the coefficients ai.
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 the Ai‘s let everyone verify that their (xi, yi) data is correct?Each person can verify thatusing the public data and their personal data, and so they can verify thatRelated postsDiscrete logarithmsSchnorr groups[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, 2q + 1 is also prime.
.