Paper 2016/643

On the Computational Overhead of MPC with Dishonest Majority

Jesper Buus Nielsen and Samuel Ranellucci

Abstract

We consider the situation where a large number $n$ of players want to securely compute a large function $f$ with security against an adaptive, malicious adversary which might corrupt $t < cn$ of the parties for some given $c \in [0,1)$. In other words, only some arbitrarily small constant fraction of the parties are assumed to be honest. For any fixed $c$, we consider the asymptotic complexity as $n$ and the size of $f$ grows. We are in particular interested in the computational overhead, defined as the total computational complexity of all parties divided by the size of $f$. We show that it is possible to achieve poly-logarithmic computational overhead for all $c < 1$. Prior to our result it was only known how to get poly-logarithmic overhead for $c < \frac{1}{2}$. We therefore significantly extend the area where we can do secure multiparty computation with poly-logarithmic overhead. Since we allow that more than half the parties are corrupted, we can only get security with abort, i.e., the adversary might make the protocol abort before all parties learn their outputs. We can, however, for all $c$ make a protocol for which there exists $d > 0$ such that if at most $d n$ parties are actually corrupted in a given execution, then the protocol will not abort. Our result is solely of theoretical interest.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint. MINOR revision.
Keywords
secure computationMPCthreshold cryptography
Contact author(s)
samuel_ran @ hotmail com
History
2017-04-28: last of 2 revisions
2016-06-21: received
See all versions
Short URL
https://ia.cr/2016/643
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/643,
      author = {Jesper Buus Nielsen and Samuel Ranellucci},
      title = {On the Computational Overhead of {MPC} with Dishonest Majority},
      howpublished = {Cryptology {ePrint} Archive, Paper 2016/643},
      year = {2016},
      url = {https://eprint.iacr.org/2016/643}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.