Assume we have a secret $s \in Z_p$. We generate the set of secret shares $\{ (x_i, s_i) \}_{i=1}^{N}$ according to a $(N,k)$ Shamir's scheme. The evaluations are generated according to the following random polynomial: $$f(x) = s + \sum_{l=1}^{k-1} t_i x^l$$ Where $t_i \gets Z_p$ are uniformly random in $Z_p$.

I am interested in statistical properties of the shares $s_i$. Can we claim they are independent and uniformly random? Additionally, can we also claim something about the joint distribution of any $k-1$ of them?

  • $\begingroup$ Did you ever hear the term perfect (threshold) secret sharing? search on our site or read on Wikipedia $\endgroup$
    – kelalaka
    Jun 1 at 15:13
  • $\begingroup$ @kelalaka: actually, "perfect secret sharing" (which states that there is no correlation between the $k-1$ shares and the value of $s$) does not mean that there's no correlation between the shares themselves. It turns out that, in this case, there isn't - however that's not directly implied by the normal security goal. $\endgroup$
    – poncho
    Jun 1 at 15:48
  • $\begingroup$ @poncho you are right, the security goal doesn't imply this, SSS it a bit too perfect. Do you know any example that fails this? $\endgroup$
    – kelalaka
    Jun 1 at 15:53
  • $\begingroup$ @poncho can you show me a reference proving that there is no correlation? $\endgroup$ Jun 1 at 17:35

If $N>k$ then the full set of shares is correlated since given any $k$ of them you can find $s$ and from it the other $N-k$.

If you take any $k$ shares, there are $p^k$ possible polynomials and $p^k$ possible tuples of shares, each of which uniquely determines a polynomial, so the distribution of share values is a permutation of the distribution of polynomials. If you know nothing about $s$, i.e. you model it as uniformly distributed like the $t_i$, then all polynomials are equiprobable and therefore so are the possible values of the shares (which also implies that they're uncorrelated). If you have information about $s$, then the shares are not uncorrelated – most obviously, if you know $s$, then the value of any share is determined by the others.

If you take any $k-1$ shares, then for any fixed $s$, the same argument implies that the shares are uniformly distributed (and so uncorrelated). For an arbitrary distribution of values of $s$, the distribution of the shares is a weighted average of uniform distributions, which is uniform.

  • $\begingroup$ Thank you for your answer. Do you know of any reference providing the same argument? $\endgroup$ Jun 1 at 19:17
  • 1
    $\begingroup$ See Claim 3.2 in eprint.iacr.org/2011/136.pdf $\endgroup$ Jun 2 at 6:28
  • $\begingroup$ This answer does not seem to correctly answer the question. Not revealing anything about the secret does not imply that the shares are distributed uniformly at random. Also, "Claim 3.2." only argues that the shares of two different secrets are indistinguishable from each other and reveal nothing about the related secrets (so it does not answer the above question either). $\endgroup$
    – Ay.
    Sep 7 at 8:40
  • $\begingroup$ @Ay. Does this edit help? The question asked me to assume that the polynomial is random, not that the shares reveal nothing about the secret. As the question is set up, one of them could even be the secret. $\endgroup$
    – benrg
    Sep 8 at 18:24
  • $\begingroup$ @benrg thanks for the edit! It seems to be some of the arguments you provided is not very convincing. For instance, you say" If you have information about $S$, then the shares are not uncorrelated – most obviously, if you know $S$, then the value of any share is determined by the others." I think, this type of arguments is not common in crypto and I've never seen it. $\endgroup$
    – Ay.
    Sep 9 at 15:12

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.