I have considered a $(t,n)$ secret sharing scheme with $n$ secret, say $a1,a2....an$. It's third party secure, but it has inside adversaries. While reconstructing secrets, a group of $t$ qualified participants upload their data to a public server.

If $t-1$ participants are cheaters, they can fool the remaining participants by changing the secrets.

How I could make this attack scheme such that the $t1$ participant can assign a chosen polynomial (i.e., chosen secrets) to fool the remaining participants. I am aware that the number of secrets is one (i.e., constant term in the polynomial), which M.Tompa & H. Woll proved.

  • $\begingroup$ To clarify, you're saying that the server is trusted and not one of the participants, and you want to know how to stop t-1 participants from colluding to prevent the secret from being reconstructed? $\endgroup$ May 16 '20 at 14:35
  • $\begingroup$ . t-1 participants are cheater. I want to know how they will modify their data such that they can cheat remaining 1 participant. $\endgroup$
    – Leo
    May 16 '20 at 15:56

I think you are mis-understanding secret sharing and what it can and cannot do. In a $(t,n)$ secret sharing scheme, the server/trusted party creates $n$ shares of the secret. At least $t$ shares must be present in order to recreate the secret from the shares. Now, if after reconstruction, the secret itself is revealed to the $t$ share holders requesting re-construction, then they each know the secret, and it is possible that the secret will be revealed milliseconds after the shares have been distributed when at least $t$ shareholders promptly send their shares back with a request for reconstruction! "Don't given me a share of the secret, just tell me the secret!" would be the rallying cry. Whether the reconstructed secret is also provided to the other $n-t$ shareholders and not just the $t$ requesters is an open question.

The way secret sharing is meant to operate is that reconstruction of the secret enables some further action (e.g. making a payment) that can be authorized by any $t$ shareholders but doesn't require approval of all $n$ shareholders. The secret is the password that is used to authorize the action. Thus, setting $t > \frac n2$ would mean a majority of the shareholders approve taking the further action and so authorize it. The secret itself is not revealed to those requesting re-construction; doing so would mean that any of the shareholders who now know the secret can carry out the further action all by themselves without the knowledge or approval of anybody else.

With this as an introduction, let us consider what the OP wants. There are $t$ shareholders who wish to reconstruct the secret, but $t-1$ of them are "cheaters" who want to "cheat" the honest participant. Well, regardless of whether valid shares are presented or are sheer gobbledygook, the trusted party will reconstruct something. For example, as I described in this answer, with Shamir secret-sharing, the secret is $$s_0 = (-1)^t (x_1x_2x_3\cdots x_t) \sum_{i=1}^t \frac{y_i}{x_i\cdot c_i}$$ where $y_1, y_2, \ldots, y_t$ are the share values as submitted by the share holders, $x_1, x_2, \ldots, x_t$ are the corresponding "locations" used in computing the shares, and $$c_i = (x_i-x_1)(x_i-x_2)\cdots(x_i-x_{i-1})(x_i-x_{i+1})\cdots(x_i-x_t).$$ There is no checking as to whether the submitted "shares" are valid or not; we get $s_0$ which is the correct secret if the shares are valid as submitted, or is gobbledygook if any of them are not. So, when the trusted party who reconstructs the secret tries to use the reconstructed gobbledygook as the password for taking the requested action, that login fails! Thus, the only question is how, if at all, the honest shareholder is cheated in all this. Well, presumably the honest shareholder wants the action to be taken, and that action will not be taken if the $t-1$ cheaters (or even just one cheater!) have submitted invalid shares. So the honest shareholder has been cheated of his desire by fickle friends who pretended to support him in in his desire but thwarted him by choosing to submit invalid shares.

Is it possible that $t-1$ cheaters can prevent reconstruction of the secret? Yes, if there are only $t$ shares available. With more shares available for reconstruction, things might be done. But we are too far afield already.


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.