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?

Improve this question
$\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, 2021 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$
    – Aydin
    Sep 7, 2021 at 16:21
  • $\begingroup$ See my updated answer $\endgroup$
    – kodlu
    Sep 8, 2021 at 4:56

3 Answers 3

Reset to default
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.

Improve this answer
$\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$
    – Aydin
    Sep 7, 2021 at 8:47
  • $\begingroup$ Your comment no longer applies to the modified answer $\endgroup$
    – kodlu
    Sep 8, 2021 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$
    – Aydin
    Sep 9, 2021 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.

Improve this answer
$\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$
    – Ilmari Karonen
    Sep 7, 2021 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$
    – Aydin
    Sep 9, 2021 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, 2021 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$
    – Aydin
    Sep 9, 2021 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, 2021 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-

Improve this answer
$\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$
    – Aydin
    Sep 7, 2021 at 13:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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