Why for achieving the fairness, less than a half of the parties should be corrupted? ($t<m/2$, where $t$ is the number of corrupted parties and $m$ is the total number of the involved parties). How should I prove it? In what kind of network this proposition holds? (Broadcast or peer to peer network)


You should definitely read the original paper by Cleve in which this was proven.

To get some intuition, imagine that $2t = m$ and consider the following

  • For the protocol to be secure, no set of $t$ corrupt parties should be able to "reconstruct" the output by themselves.
  • For the protocol to be fair, the set of $m-t=t$ honest parties should be able to "reconstruct" the output by themselves.

Now, the problem is that you cannot distinguish which parties are corrupt and which are honest (otherwise the MPC problem would be trivial: simply discard the malicious nodes and work only with the honest ones), so you need to satisfy the two conditions above for any set of $t$ parties, which is clearly a contradiction.

| improve this answer | |

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.