2
$\begingroup$

I'm curious about the honest minority case and what cryptographers have and are currently using to get around this. My motivation is primarily the MPC space, but I'm sure there are other subfields that encounter it.

Some thoughts of mine include:

  • It seems that a high threshold Shamir Secret Sharing Scheme or just a vanilla additive sharing scheme would be required to operate on inputs while protecting privacy in a dishonest majority setting, however this does nothing to mitigate the fact that the adversary could easily compromise correctness.
  • I know SPDZ technically handles the dishonest majority case, my limited understanding of SPDZ is that they basically MAC everything and anything to accomplish this, but their approach also only provides safety from prying eyes and not any kind of probabilistic or computational guarantee of correctness.

I'm curious, is there some impossibility result in this area that I am just not aware of? It feels like there ought to be, because an adversary with that kind of control should be able to change the inputs of her puppets to compromise the output. Maybe if we limit the adversary to corrupting parties until after their inputs are initially submitted/distribute/broadcast we can say something of value?

$\endgroup$
2
$\begingroup$

There is a model, typically called proactive security (and sometimes also called a mobile adversary), that considers the case that parties can be corrupted and later uncorrupted. Time is divided into epochs and security holds as long as the appropriate threshold of parties is honest in each epoch. In the dishonest majority case, this means that unless all of the parties are corrupted in a single epoch, security is preserved. These protocols work by rerandomizing secret sharing and enforcing correctness.

$\endgroup$

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.