1
$\begingroup$

I was thinking of this since yesterday. Imagine, a secret is split into its respective shares (using any secret sharing scheme) with threshold $t$ and total $n$. Can we find out given any random string if it is a valid share of the secret ?

Of course without brute force approach, i.e splitting the secret into its shares and matching the string with each of its member to find out if its legitimate member.

Is it possible at all ? for any secret sharing mechanism ? So to summarize, given a string $s_i$ ,a secret string $secret$ and any configuration parameters needed (say $t,n$ values etc) to share secret.

Can we identify if $s_i$ is valid $secret$ without brute force approach described above ?

$\endgroup$
3
  • $\begingroup$ I suspect this kind of distinguishing ability would break the information-theoretic security of the Shamir scheme, but I'm not sure. $\endgroup$
    – pg1989
    Commented Sep 22, 2014 at 6:14
  • $\begingroup$ @pg1989 the distinguishing ability may break some security if other parameters like $t,n$ are not made available etc. here we are only speeding up the process of identifying the membership $\endgroup$
    – sashank
    Commented Sep 22, 2014 at 6:37
  • $\begingroup$ If you assume knowledge of $t-1$ shares and not the secret, then you can exclude possible shares for the one you are missing by checking membership. This breaks information theoretic security. $\endgroup$
    – tylo
    Commented Sep 22, 2014 at 11:12

1 Answer 1

1
$\begingroup$

Just to be specific we are talking about information theoretically secure secret sharing, e.g. Shamir sharing. Lets say a secret $secret$ is shared in $n$ shares $S = \{s_1, \ldots, s_n\}$. Assume further party $P_i$ is given share $s_i$. If I understand your question correctly, you are asking if we give $P_i$ some share $r \ne s_i$ is there anyway for $P_i$ to decide if $r \in S$?

If that is the question, I think the answer is, "no", since it would contradict the properties of secret sharing.

Here is my argument: Assume we give $P_i$ some help. We give her $t - 2$ shares from $S\backslash \{s_i, r\}$. Now $P_i$ has $t - 1$ shares of $secret$. Now $P_i$ can take $r$ and in total have $t$ shares (possibly with one share not being correct). This is enough to reconstruct some secret $secret'$. If and only if $r \in S$ we have "secret' = secret". So if $P_i$ could tell if $r \in S$, then $P_i$ would know whether or not $secret' = secret$. However, this contradict the property of secret sharing that $t - 1$ shares gives no information on the secret.

In fact since this is information theoretic security even a brute force attack will make no difference.

$\endgroup$
6
  • $\begingroup$ $P_i$ knows the secret and t,n parameters also. $\endgroup$
    – sashank
    Commented Sep 22, 2014 at 11:04
  • $\begingroup$ If $P_i$ knows the secret, there's no point giving $P_i$ a share, because it generated it. The information theoretic aspect is correct tho: If a party without the secret but only a share can find out if a share is valid, it leans something about the secret already. This isn't information theoretic secure any more. $\endgroup$
    – tylo
    Commented Sep 22, 2014 at 11:10
  • $\begingroup$ Of course if $P_i$ generated the sharing the question is trivial. $P_i$ knows all the shares. On the other hand $P_i$ could be given $secret$ and $s_i$ by a dealer that generated the sharing. In that case $P_i$ would not know the shares in $S\backslash \{ s_i \}$. Is that the setting you are considering @sashank? $\endgroup$
    – Guut Boy
    Commented Sep 22, 2014 at 12:05
  • $\begingroup$ Information theoretically, this is the almost same case as knowing two shares and wanting to get the secret or a 3rd share. If you have a way to verify something, you can eliminate certain input or output values. And that breaks this type of security. The reasoning is similar to that of Shannon for perfect secrecy of OTP. $\endgroup$
    – tylo
    Commented Sep 22, 2014 at 12:21
  • $\begingroup$ @GuutBoy, yes am considering the setting you described $\endgroup$
    – sashank
    Commented Sep 22, 2014 at 12:26

Your Answer

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

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