Secret-sharing with polynomials

Suppose you have a secret you wish to transmit to $n$ people, but in such a way that all of those $n$ people must collaborate in order for the secret to be revealed. In other words, it must not be possible for even $n-1$ of those people to obtain the secret, even partially, if the $n$th person does not cooperate.

Using a suitable encoding scheme, express the secret as an element $s$ of the field $\mathbf{F}_p$, for a prime $p > n$ (of course it is assumed that the recipients know how to obtain the secret from $s$). Choose at random a vector $\mathbf{a} = (a_1,\dots,a_{n-1}) \in \mathbf{F}_p^{n-1}$ and construct the polynomial
\[ P = s + a_1X + a_2X^2 + \dots + a_{n-1}X^{n-1} \in \mathbf{F}_p[X]. \]
Finally, compute $P(i)$ for $i = 1,\dots,n$ (the values of $i$ must all be distinct and not zero, which is why we work in $\mathbf{F}_p$ with $p > n$); each recipient gets one of the pairs $(i,P(i))$.

If all the recipients cooperate, from the $n$ pairs $(i,P(i))$ they can reconstruct $P$ using polynomial interpolation: since the values of $i$ are all distinct, it is guaranteed that there is exactly one suitable polynomial $P$. The secret is then simply $P(0)$ (this is why we must not use $i = 0$ above!).

On the other hand, if only $n-1$ pairs $(i,P(i))$ are available, then for each $k$ there is exactly one polynomial $P$ which matches the given pairs and such that $P(0) = k$ (since then the pair $(0,k)$ gives a $n$th pair, which then gives a unique polynomial). Thus all values of the secret are equally likely to be the correct one, meaning that no information about the secret is given.

This scheme can be implemented using Sage as follows:

def Sharing(p, n, s):
    if p <= n:
        return None
    pr.<x> = PolynomialRing(GF(p))
    P = s
    for i in range(1, n):
        P = P + ZZ.random_element(p)*x^i
    return [(i, P(x=i)) for i in range(1, n+1)]

def Decoding(p, pt):
    pr.<x> = PolynomialRing(GF(p))
    P = pr.lagrange_polynomial(pt)
    return P(x=0)

The function Sharing() takes as input the prime p, the number n of recipients and the secret s, and outputs a list of the secrets to be given to each recipient. The function Decoding() takes as input the list of secrets of each recipient, and outputs the shared secret:

sage: pt = Sharing(11, 10, 5)
sage: pt
[(1, 9),
 (2, 0),
 (3, 6),
 (4, 2),
 (5, 8),
 (6, 7),
 (7, 2),
 (8, 7),
 (9, 5),
 (10, 4)]
sage: Decoding(11, pt)

If not all the secrets are available, however, it will give a possibly incorrect result:

sage: pt.pop()
(10, 4)
sage: pt
[(1, 9), (2, 0), (3, 6), (4, 2), (5, 8), (6, 7), (7, 2), (8, 7), (9, 5)]
sage: Decoding(11, pt)

In fact, since all the results are equally likely (as we discussed above), if not all the secrets are available, the decoding function behaves like a random function. The result it gives may or may not be the correct one; there is no way to know without knowing the last piece of the secret.

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.