Shamir Secret sharing - Can share generator keep x values secret?

Question

I'm wondering, in Shamir secret sharing, can generator of the shares, keep the x values which are used in evaluating the polynomial to obtain y values (i.e., the shares) secret, and whenever the original secret is needed, he retrieves the t shares and reconstructs the secret? In this setting the share holders should not be able to construct the secret even all of them collude. Is there any secure way of doing so?

Answer 1

Each share in Shamir-type secret-sharing schemes has two parts: the share value $f(x_i)$ which is the value taken on by a certain polynomial $f(\cdot)$, and the share "location" $x_i$. The "dealer" who constructs the shares and hands them out to individual shareholders is assumed to have handed out $(x_i, f(x_i))$ to the $i$-th share holder. In this scenario, any $k$ (or more) shareholders in a $(k,n)$ scheme can get together and reconstruct the secret, and fewer than $k$ shareholders cannot reconstruct the secret.

If the dealer hands out only $f(x_i)$ to the $i$-th share holder and merely makes a note in his records that the $i$-th share holder's share location is $x_i$, then only the dealer can reconstruct the secret when $k$ or more shareholders make an application to the dealer; the $k$ shareholders cannot reconstruct the secret by themselves because while they all know their share values, they do not know the location of those shares. This scheme is, of course, fraught with danger in case the dealer's list is lost or is corrupted in various ways: the secret might be irretrievably lost.

See also this answer for how enemies can attack a Shamir-type secret sharing scheme by tampering with share values and by tampering with share locations, and how to get around such problems.

Answer 2

Sure the dealer can do that. The real question is, what kind of security does it provide? If the attacker can verify when he has found the right $x$ values, then at best the security of the scheme is computational in the size of the underlying finite field. If the attacker cannot verify when he has found the right $x$ values, the security may be information theoretic. Prior work (Security Limitations of Using Secret Sharing for Data Outsourcing by Dautrich and Ravishankar) has found that for $k$-out-of-$n$ (where $k<n$), if the attacker can gather $k+2$ shares, even without knowing the $x$ values, the attacker is able to recover the secret. It is unclear exactly how this applies when $k=n$, though it at least makes one feel uncomfortable.

Fear not, however, there is a better way to do it that has been well studied. You never specify how many of the recipients must work with the dealer to recover the secret. In other words, do all the recipients have to send their shares back or only some fraction? I'll assume it is some threshold $t$ (which could be all of them).

The answer is to do 2 layers of secret sharing. The dealer begins by using xor-sharing to split the secret into two shares. This is done by picking a random value $r_1$ and setting $r_2=r_1\oplus s$ (where $s$ is the original secret to be shared). The dealer keeps $r_1$. Then shares $r_2$ with the other people using standard t-out-of-n Shamir Secret Sharing (or if $t==n$, you can again use xor-secret sharing).