0
$\begingroup$

Let $t$ be a threshold in the Shamir secret sharing (SSS) scheme.

Assume we know $t'<t$ shares. Assume we are given some random values picked uniformly from the same field as the one used in SSS.

Question: can we distinguish the random values from the shares with a non-negligible probability?

$\endgroup$
3
  • 1
    $\begingroup$ In the answers, we find three potential interpretations of the scenario you are asking about. Could you refine your answer to list which one was actually intended (or if your actually meant a fourth interpretation)? $\endgroup$
    – poncho
    Sep 7 at 16:19
  • $\begingroup$ @poncho Thanks for your answer below! Sure, I will carefully read your answer and try to improve my question. If you don't mind, I will do that in a couple of days. Many thanks again. $\endgroup$
    – Ay.
    Sep 7 at 16:21
  • $\begingroup$ See my updated answer $\endgroup$
    – kodlu
    Sep 8 at 4:56
2
$\begingroup$

Each value of the degree $t-1$ full SSS polynomial $P$ evaluated at any $x$ in the finite field $F$ it is defined over is uniformly distributed in $F$. See this answer for example.

Now assume $t’<t$ shares are revealed, say they are $S’=\{(x_1,P(x_1)),\ldots,(x_{t’},P(x_{t’}))\}.$

If the original set of shares was $S$ the nonempty set $T=S\setminus S’$ now uniquely determines in the usual way a valid Lagrange interpolation polynomial of degree $t-t’-1$ given any $t-t’$ points $x$ in $K \setminus \{x_1,\ldots,x_{t’}\}$.

Distinguishing Algorithm: Let $k>t-t’$ and let claimed shares $$C=\{(x_j,y_j):1\leq j \leq k\}$$ be given. If these are genuine shares any $t-t’$ of them will give the same Lagrange Interpolation polynomial as any other such subset of the same size. If the $y_j$ are random, two distinct Lagrange interpolations say two supported on $$A=\{x_1,\ldots,x_{t-t’}\}$$ and on $$A’=\{x_2,\ldots,x_{t-t’},x_{t-t’+1}\}$$ will give different Lagrange interpolation polynomials with probability $$1-\frac{1}{q}$$ where $q$ is the size of the field we are using.

In fact even if only one share in $A \bigcup A’$ is random, this property will hold since at least one of the interpolations will yield a random polynomial.

$\endgroup$
3
  • 1
    $\begingroup$ Thanks for the answer. However, the y-coordinated are not independent (and are correlated), as they are the evaluation of a fixed polynomial at different values. Also, the same coefficients are reused for different x-coordinates. Therefore, we cannot argue the distribution of the shares for two different x-coordinates by relying on the distribution of the coefficients. Here is simpler example; consider $y_1=r_1. a+r_2$ and $y_2=r_1. b+r_2$, where $r_i$ is distributed uniformly at random. We cannot argue that $y_1$ and $y_2$ are independently distributed $\endgroup$
    – Ay.
    Sep 7 at 8:47
  • $\begingroup$ Your comment no longer applies to the modified answer $\endgroup$
    – kodlu
    Sep 8 at 1:33
  • $\begingroup$ thanks for the answer. I think, even if we assume only one share is random, we cannot assume that the next shares are random too, because the rest will rely on the randomness used on the first share (n other words the randomness is being reused). However, it might be easier to argue the randomness, if the x-coordinates are random values (which I'm not assuming) $\endgroup$
    – Ay.
    Sep 9 at 15:05
2
$\begingroup$

Assume we know $t'<t$ shares. Assume we are given some random values picked uniformly from the same field as the one used in SSS.

Question: can we distinguish the random values from the shares with a non-negligible probability?

It depends.

Now, there are two possible ways to interpret your question (and while the answer is the same for both, the logic differs slightly). Here are the ways I see:

  • These $r$ 'random values' are to be considered all at once as potential shares; that is, the adversary was given a total of $t' + r$ shares, $t'$ of which are true shares, and $r$ of which might be random values, or (as far as the adversary was concerned) might also be true shares. If that's the case, follow the logic below.

  • These $r$ 'random values' are all possibilities of the missing share. That is, $r-1$ of them are random values (and the adversary knows that), that last value might also be a random value, or it might be a true value - the adversary doesn't know which, and he also doesn't know which might be the true value. If that's the case, follow the logic below, but with $r=1$, and iterate through the various possibilities for the honest share.

I'll also assume that the attacker has some knowledge of what the shared secret might be; he might not know the exact value, but he might know the value to be one of a small set of possibilities (or at least, know that there are a large set of values that it can't be).

In that case, if $t' + r < t$, then the adversary cannot determine anything; all these shares look random. That is, for any values of the known shares, and any value of the shared secret, there are possible coefficients to the unknown polynomial that would make that lead to the observed values (and it turns out that there's an equal number of possibilities independent of the observed values, hence the adversary can't even get any probabilistic information).

On the other hand, if $t' + r \ge t$, then the adversary does have an approach; he can take the shares he has (both the known good ones, and the ones with questionable providence), and reconstruct what shared secret they would imply; he would then check to see if that shared secret was possible. If it's not one of the possible values, he knows that some of the shares he used were incorrect.

$\endgroup$
6
  • $\begingroup$ I originally assumed a third interpretation: the adversary is given two sets of $t'$ values, one of them being a subset of the shares generated by Shamir's scheme with threshold $t > t'$ and the other set consisting of $t'$ uniformly distributed random numbers; can the adversary distinguish the two sets with probability $> \frac12$? (FWIW, the answer to this interpretation of the question is obviously "no, it cannot", based on essentially the same argument as you give above.) $\endgroup$ Sep 7 at 16:15
  • $\begingroup$ thanks to both for your answer and comment! I meant the 1st case (or 3rd one). However, I'm not sure about the indistinguishability of true shares from random values. Because the shares are correlated and their randomness stems from the same coefficients used for all shares. $\endgroup$
    – Ay.
    Sep 9 at 14:57
  • $\begingroup$ @Ay.: And so my answer of 'he can iff $t' + r \ge t$' is what you were looking for? $\endgroup$
    – poncho
    Sep 9 at 15:55
  • $\begingroup$ @poncho well basically the adversary does not have all the shares to check if a subset of them can lead to the secret. $\endgroup$
    – Ay.
    Sep 9 at 16:08
  • $\begingroup$ @Ay.: yes, and an insufficient number of shares (counting partial knowledge of the shared secret as effectively an additional share) looks random... $\endgroup$
    – poncho
    Sep 9 at 16:59
0
$\begingroup$

No we can't. We know that SSS is perfect that means knowledge of (t-1) or fewer shares provides no information about s -therefore about other shares-

$\endgroup$
1
  • 1
    $\begingroup$ Thanks for the answer. However, revealing nothing about the secret does not imply that each share has the same distribution as a truly random value. Thus, your answer does not seem to fully answer my question. $\endgroup$
    – Ay.
    Sep 7 at 13:30

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.