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$
  • $\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 Sep 22 '14 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 Sep 22 '14 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 Sep 22 '14 at 11:12
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$
  • $\begingroup$ $P_i$ knows the secret and t,n parameters also. $\endgroup$ – sashank Sep 22 '14 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 Sep 22 '14 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 Sep 22 '14 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 Sep 22 '14 at 12:21
  • $\begingroup$ @GuutBoy, yes am considering the setting you described $\endgroup$ – sashank Sep 22 '14 at 12:26

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.