Checking the share membership in secret sharing schemes

Question

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 ?

Answer 1

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.