1
$\begingroup$

I need to know whether one can obtain any roots of the polynomial in Shamir secret sharing if he possesses less than threshold shares.

For instance in (t,n) if he has t-1 shares can he obtain any roots of the original polynomial?

** Here we assume that the polynomial has some roots.

$\endgroup$
  • $\begingroup$ Why do you want to know that? Unless it's just idle curiosity, I'm pretty sure that you're asking the wrong question. $\endgroup$ – CodesInChaos Sep 26 '14 at 12:53
  • $\begingroup$ I have a d degree polynomial P1, I pick 2d+1 (or more) points at random and evaluate P1 on these points. I give away only Y's value to the server. You have P2, with the same degree as mine. You evaluate P2 on the same points as I did and you only send your Y's to the server. Now the question is 1) Can the server learn any of our polynomial having only Y's. 2) Can he infer even a few roots of our polynomial? $\endgroup$ – user153465 Sep 26 '14 at 13:01
  • $\begingroup$ In Shamir's secret sharing, a share consists of both the $x$ and $y$ coordinates of the point; in your comment, you appear to imply that you're sharing only the $y$ coordinates. Which is it? $\endgroup$ – poncho Sep 26 '14 at 14:05
  • $\begingroup$ Yes, exactly, the problem I stated in the comment is a bit more difficult than the main question (the title). I would like to stick with the main question, to see given both values can anybody infer the roots. $\endgroup$ – user153465 Sep 26 '14 at 14:09
  • $\begingroup$ 1) Since shares can have a 0 y value they can be roots, in which case the attacker trivially learns some roots. 2) What you describe in your comment has almost nothing to do with SSS, except that both use polynomials in finite fields. 3) Just to be sure, with roots you mean the points at which y=0 and not the coefficients of the polynomial, right? $\endgroup$ – CodesInChaos Sep 26 '14 at 14:51
2
$\begingroup$

If you have $t-1$ shares of an $(t,n)$ system, you have a chance at learning of the roots of the system... as long as some of your shares have a 0 for the $y$ coordinate. You can't learn any other roots.

Demonstration that the possession of a share with a $y$ coordinate of 0 gives you knowledge of a root (and forgive me if this is too obvious):

  • A share in Shamir's scheme is a pair $(x, P(x))$, where $x$ is a nonzero coordinate, and $P(x)$ is the secret polynomial evaluated at that coordinate. If the $y$ coordindate listed happens to be 0, we have $P(x) = 0$, which is pretty much the definition of $P$ has a root at $x$.

Demonstration that the attacker cannot learn any roots at locations other than the $x$ coordinates for the shares he has:

  • Consider what would happen if he could. By learning of a value $x'$ which does not appear as an $x$ coordinate for any of the shares he has, and for which $P(x')=0$, he could treat that as another share $(x', 0)$, and use that, and his $t-1$ existing shares, and learn the entire polynomial. We know he can't do that, and so he can't learn such an $x'$
$\endgroup$
  • $\begingroup$ Many thanks. Since you answered very precisely I must ask you some questions if you don't mind. $\endgroup$ – user153465 Sep 26 '14 at 15:06
  • $\begingroup$ Referring back to the question I stated in the comment; if we generate far more than threshold Y's,using random X's, then we outsource only Y's . Can the adversary find the polynomial or even a root of this polynomial? Why? $\endgroup$ – user153465 Sep 26 '14 at 15:17
  • $\begingroup$ @user153465: the attacker cannot find any roots (unless P happens to be the trivial polynomial $P(x)=0$); this can be seen by the observation that we can take the secret polynomial $P(x)$ and replace it with $P(x+c)$ and all of the secret $x$ coordinates $x_i$ with $x_i-c$. This doesn't change what the adversary sees, but changes where the roots are. $\endgroup$ – poncho Sep 26 '14 at 15:22
  • $\begingroup$ This is a bit vague to me. Could you make it more clear please. $\endgroup$ – user153465 Sep 26 '14 at 15:31
  • $\begingroup$ @user153465: to the question "can the adversary find ... even a root...", I answered he "cannot find any roots (except in one specific case)". I don't know how to make it any more clear than that; the observation was that, given a specific $P$ (with roots at specific locations) and $x$ values, we can find a $P'$ and $x'$ values with $P(x)=P'(x')$; $P'$ has roots at different locations, however the adversary sees only $P(x) = P'(x')$, hence he has no information whether he's dealing with $P$ or $P'$. $\endgroup$ – poncho Sep 26 '14 at 22:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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