Why for achieving the fairness and guaranteed output delivery, 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)

Would you please prove it intuitively?

  • 1
    $\begingroup$ You will never reach true understanding if you ask for "intuitive proofs" of everything. Formal proofs exist for a reason. $\endgroup$
    – fkraiem
    Commented Sep 2, 2018 at 12:37
  • $\begingroup$ @fkraiem Could you please give me a formal proof? $\endgroup$ Commented Sep 2, 2018 at 13:01
  • 3
    $\begingroup$ You have been somewhat monopolizing the site, with 14 questions in a few days (plus follow-up questions on every answer). Your questions show confusion about very fundamental aspects of MPC. If you really want to understand MPC, you need to slow down so you have time to process. You cannot crowdsource every single step in understanding. Maybe the books are not a good fit and you would get more by watching some tutorial lectures (e.g., Bar-Ilan winter schools). $\endgroup$
    – Mikero
    Commented Sep 2, 2018 at 15:36
  • $\begingroup$ @Mikero Thanks a lot for considering my question. I have just put my questions here, but I did not force anyone to answer my questions. If you and anybody else get a chance, please steer me in a right direction. Thank you, Mikero $\endgroup$ Commented Sep 2, 2018 at 17:40
  • 1
    $\begingroup$ I never said it was against site rules to ask so many questions. I am trying to steer you in a right direction by suggesting that you slow down and make a serious effort to understand one thing before moving on to the next. $\endgroup$
    – Mikero
    Commented Sep 2, 2018 at 19:48

1 Answer 1


Intuitively anything the honest minority can do the dishonest majority can do as well. So if the minority can force a correct outcome the majority can force an incorrect outcome.

Side note:The question is ill-defined, not mentioning a specific problem where these requirements are to be held, is this a computation? who has the input? In some situations we can deal with a dishonest majority such as limiting them to no more than failing the process.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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