Formal Proof of Shamir's Secret Sharing Scheme Security

Question

Shamir's Secret Sharing scheme is perfectly secure.

Could you please suggest where I can read a formal proof of Shamir's Secret Sharing scheme being perfectly secure?

Answer 1

Let's recall Shamir's Secret Sharing. We work in a finite field $\mathbb{F}_q$ of cardinal $q$. The secret to share is $s$; we want $n$ shares with a threshold $t$. We suppose that $n < q$ (otherwise, the scheme does not work). We conventionally name $n$ non-zero values of $\mathbb{F}_q$: $x_1$, $x_2$... $x_n$. Exactly how we choose them is unimportant, as long as they are all distinct from zero and from each other, and everybody knows which is which. If $q$ is prime (field $\mathbb{F}_q$ is $\mathbb{Z}_q$, i.e. the integers modulo the prime $q$), then we will traditionally choose $x_i = i \bmod q$ (since $n < q$, this works: none of the $x_i$ is zero, and they are all distinct from each other). By convention, I also define $x_0 = 0$ (this will help in my notations).

To share $s$, we generate a random polynomial $A = \sum_{i=0}^{t-1} a_i X^i$, where:

• $a_0 = s$
• For all $i = 1$ to $t-1$, $a_i$ is chosen randomly and uniformly in $\mathbb{F}_q$ (notably, each $a_i$ can be zero with probability $1/q$).

By construction, $A(0) = s$. The share of each user $i$ is $v_i = A(x_i)$. The polynomial $A$ has degree "at most $t-1$" (degree of $A$ may be lower than $t-1$ since it is possible that $a_{t-1} = 0$).

To rebuild the secret, $t$ share holders use their respective shares to recompute polynomial $A$, and thus compute $A(0)$, which is the secret Reconstruction uses the Lagrange polynomial. I now suppose that the shares used for reconstructions are $v_1$, $v_2$,... $v_t$ (this simplifies notations, but since the conventional naming of $x_1$, $x_2$... is arbitrary, this assumption that not reduce generality). We define the Lagrange polynomial $L_i$ as the polynomial of degree $t-1$ such that $L_i(x_i) = 1$, but $L_i(x_j) = 0$ for any $j \neq i$ (for $1\leq i,j\leq t$). The Lagrange polynomial is computed as: $$ L_i = \frac{\prod_{1\leq j\leq t, j\neq i}(X - x_j)}{\prod_{1\leq j\leq t, j\neq i}(x_i - x_j)} $$ Since all the $x_j$ are distinct from each other, the denominator is necessarily non-zero, so the division works; and with $L_i(x_i)$, numerator and denominator end up being identical products, this $L_i(x_i) = 1$.

With Lagrange polynomials, one can find a matching $A$ has: $$ A = \sum_{i=1}^{t} v_i L_i $$ Since then: $$ A(x_j) = \sum_{i=1}^{t} v_i L_i(x_j) = v_j $$

That $A$ is the unique solution can be proven with a counting argument: there are exactly $q^t$ possible tuples $(v_1, v_2,\cdots v_t)$ ($t$ values in $\mathbb{F}_q$), and, for each of them, the reconstruction with Lagrange polynomials yields a matching polynomial $A$ of degree at most $t-1$. However, there are only $q^t$ polynomials of degree at most $t-1$. Thus, there cannot be more than one matching polynomial per tuple; otherwise, you'd run out of polynomials at some point.

(It is in fact a more general result that a polynomial of degree at most $t-1$ is uniquely defined by its values over $t$ distinct inputs; this also works in infinite fields. A special case is for $t = 2$, and this really means that by any two distinct points, there passes exactly one line. The general result is proven with more algebra; for finite fields, the counting argument above is a lot simpler.)

Note that secret reconstruction is interested only in the secret $s = A(0)$; having the complete polynomial is only a mean to that, and it is not fully necessary. Indeed, we have: $$ s = A(0) = \sum_{i=1}^{t} v_i L_i(0) $$ The values $L_i(0)$ depend on which share holders are involved (i.e. the choice of $x_1$, $x_2$... $x_t$), but not the share values ($v_1$, $v_2$... $v_t$). Thus, the $L_i(0)$ can be precomputed. This is especially convenient when doing multiple reconstructions with the same share holders; one typical case is when working with $q = 256$ (the finite field with exactly 256 elements) and applying Shamir's Secret Sharing on byte-per-byte basis on a multi-byte secret value.

The security of the scheme hinges on the following result: for any set of $t$ values in $\mathbb{F}_q$, there is exactly one matching polynomial $A$.

To simplify notations, I now suppose that you have shares $v_1$, $v_2$... $v_{t-1}$. These are $t-1$ shares, i.e. less than the threshold. To prove the absolute security of the scheme, we need to show that these $t-1$ shares yield no information whatsoever on the secret $s$. To do that, we note that: $$ s = A(0) = \sum_{i=1}^{t} v_i L_i(0) $$ Therefore: $$ v_t L_t(0) = s - \sum_{i=1}^{t-1} v_i L_i(0) $$ Note also that $L_t(0) \neq 0$: $$ L_t(0) = \frac{\prod_{1\leq j\leq t-1}(0 - x_j)}{\prod_{1\leq j\leq t-1}(x_i - x_j)} $$ (All the $x_j$ and all the $x_i-x_j$ are non-zero, so the products are non-zero.)

It follows that, given share values $v_1$ to $v_{t-1}$, for any possible value of $s$, there is exactly one value of the missing share $v_t$ that would yield that $s$. Thus, the $t-1$ shares $v_1$ to $v_{t-1}$ yield no information at all about the secret, since all possible values of the secret are still possible and equiprobable at that point.

Note the subtlety here about "equiprobability". The counting argument says that there are exactly $q^{t-1}$ polynomials $A$ of degree at most $t-1$ such that $A(0) = s$, for a given secret $s$. With $t-1$ shares, i.e. knowledge of $t-1$ values $v_i = A(x_i)$, you don't know enough to pinpoint a single polynomial $A$; in fact, you have exactly $q$ matching polynomials, one for every possible value of the secret $s$. This establishes a bijection between the possible values of the secret $s$, and the possible values of the missing share $v_t$ (the formula above makes that bijection explicit). The bijection transports the information: every piece of information, even statistical, that you may know on the secret $s$, can be transformed through the bijection into the same information on the missing share $v_t$, and back. This really means that the $t-1$ shares, by themselves, teach you nothing more. Real-life secret values $s$ are not completely random and uniform, but that's not the point; the point is that without the missing share $v_t$, you don't know more on $s$ than you already knew about it before. This is the sense in which Shamir's Secret Sharing is unconditionally secure.

Some extra notes:

• All of this hinges on the idea that the initial sharing polynomial $A$ was chosen really randomly and uniformly. In practice, this is not easily achieved: "true" randomness is elusive. We customarily use pseudorandom generators that expand a given seed, assumed "random", into an arbitrarily long sequence of bytes that are indistinguishable from randomness... as long as attackers have finite computing resources that do not exceed a given value. Moreover, the "seed" itself is obtained from some physical process which is supposed to be unpredictable, but this also assumes limitations on the abilities of attackers at obtaining information from the physical world. Thus, the "unconditional" security of Shamir's scheme is actually conditional on a number of other things.

  (Physicists tell us that there is a fundamental uncertainty about the state of any physical system, but not many alleged "random generators" really tap into that. Moreover, from an epistemological point of view, using a quantum-uncertainty-powered RNG is not "stronger" than a cryptographically secure PRNG; you are just putting more trust in Niels Bohr than in Alan Turing.)

• The security of the scheme relies on the fact that the polynomial $A$ is single-use. If you use the scheme to do a byte-per-byte sharing of a multibyte secret value, then you MUST generate a new random polynomial $A$ for every byte that is to be split into shares. If you reuse the same $A$ for several bytes, then all the security goes to naught.

• A practical implementation may leverage the bijection between share tuples and polynomials, by NOT generating the coefficients $a_i$ randomly; instead, it would generate the first $t-1$ shares randomly and uniformly, then compute shares $v_t$, $v_{t+1}$,... $v_n$ with formulas such as the one described above, where the $L_i(0)$ values can be precomputed (even hardcoded in the implementation source code). The bijection guarantees that this is safe.

Answer 2

Shamir gives it in the paper which presents his scheme here: How to Share a Secret