Sorry if this is a stupid question, but: in Shamir's scheme, we construct a polynomial and make our secret $S$ the zero-th coefficient $a_0$. What, if anything, necessitates this - in other words, can we make include $S$ as $a_1$ or any other coefficient?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
In Shamir's scheme is a secret sharing scheme, that is, someone that has fewer shares than is required get no information about the secret. For example, if we have a system where we require 3 shares to reveal the shared secret, then someone with 2 shares cannot be able to reconstruct it.
This is true if we make the shared secret the zero-th coefficient; with $N-1$ shares, every possible value for the zero-th coefficient is equally possible.
This turns out to be also true for the (N-1)th coefficient; however it turns out not to be true for any intermediate coefficient.
Here's a simple example to illustrate this; suppose we pick the field $GF(5)$, and we select $N=3$ (and is, 3 shares are required to reveal the secret); hence we pick a quadratic with the secret as one of the coefficients.
Then, we distribute the shares; in this example, two of the shares we distribute are $(1, 1)$ and $(4, 0)$; that is, the holder of those two shares know that, for the secret polynomial $P$, we have $P(1) = 1$ and $P(4) = 0$.
Now, the holder of two shares should not be able to reconstruct the secret; however what they can do is list all the quadratics that are consistent with the values he does know. There are five possible polynomials with degree at most 2 that meet the criteria:
$$0x^2 + 3x + 3$$
$$1x^2 + 3x + 2$$
$$2x^2 + 3x + 1$$
$$3x^2 + 3x + 0$$
$$4x^2 + 3x + 4$$
It is easy to confirm that plugging in $x=1$ and $x=4$ into the above polynomials will result in the known values 1 and 0.
Now, our attacker knows that one of these five equations are the secret one, but he has no information on which it can be. If the shared secret were the 0th or the (N-1)th coefficient, we can see that he learns nothing; all values are equiprobable. However, if the shared secret were the middle coefficient, well, all these polynomials have a middle coefficient of 3, and so the attacker would have learned the secret, even though he shouldn't have been able to.
This sort of thing can happen to any of the middle coefficients; the only safe coefficients are the first and the last.
---- UPDATE ----
Ok, I found a case where a middle coefficient is also safe; that is the case where the field has characteristic 2 (i.e. is $GF(2^n)$ for some $n$), and $N=3$. In that specific case, it turns out that the behavior I listed above cannot happen; all $2^n$ possible equations (when $N-1$ shares are known) will have different values for the $x$ coefficient. I believe that this specific case is the only example of a situation where an intermediate coordinate is safe; that in all other cases, you can find $N-1$ shares so that an intermediate coordinate is determinable with $N-1$ shares.
-
$\begingroup$ why is that? why in the case of GF(2^n) and N=3 that behavior can't happen? $\endgroup$– user25471Commented Jul 7, 2015 at 9:32
-
$\begingroup$ @bitanic: well, in the case of $N=3$, the middle coefficient is leaked if the two distinct shares x-coordinates $x_1, x_2$ have $x_1 + x_2 = 0$ (which, if you notice in my example, is exactly the case; $1+4 = 0$ in the field). However, in $GF(2^n)$, this relationship holds only if $x_1 = x_2$, and so the two shares are actually the same (and so the attacker doesn't actually obtain enough information). $\endgroup$– ponchoCommented Jul 7, 2015 at 13:05