Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question
3  
It would be neater (in my mind) for the generator to use xor-sharing first, then standard Shamir secret sharing. –  figlesquidge May 21 at 18:18
add comment

2 Answers 2

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.

share|improve this answer
    
Hi, First thanks for your comment. Indeed,I`m not worried about tampering with shares as I have sort of macs to verify the shares. Thus my main concern is how shareholders can attack it and learn the secret. –  user13676 May 21 at 18:59
    
Additionally, we can only store i as an index and use pseudo-random generator to obtain Xi when reconstructing the secret. –  user13676 May 21 at 19:13
add comment

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 (kudos to OP for finding this paper) 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).

share|improve this answer
    
Hi, Many thanks for your reply. You assumed right, it`s threshold t and assuming that all recipient can collude to construct the secret. In terms of your solution, I think it won`t work in my system as all shares are going to be multiplied or added by some values. –  user13676 May 21 at 19:11
    
@user13676, if I get this straight, you want to allow all the share holders to compute on the shares without the dealer needing to participate, then allow the dealer to reconstruct the output. At the same time, it is possible that all share holders are corrupt. Is that correct? My solution is an answer to the question as posed. If you have additional requirements, they should be in the question (though at this point you may be best off asking a new question on the site). –  mikeazo May 21 at 19:22
    
@user13676 if you do ask another question on the site, I'd suggest keeping it as generic as possible. Basically it seems like you want outsourced computation where privacy is preserved even if all the computation servers are malicious. –  mikeazo May 21 at 19:24
    
How can I formally prove that its secure? –  user13676 May 21 at 19:25
    
@user13676 Given the shares, each possible secret value (reconstructed using some vector of x values) must be equally likely. Show that this holds, and you will formally prove that it is secure. –  mikeazo May 21 at 19:28
show 2 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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