Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question
add comment

1 Answer

up vote 8 down vote accepted

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.

share|improve this answer
    
It's very clear now, thanks! –  Chiffa Dec 23 '13 at 17:28
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.