On the computational overhead of MPC with dishonest majority

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review

  • Jesper Buus Nielsen
  • Samuel Ranellucci, Department of Computer Science, George Mason University, Department of Computer Science, University of Maryland, Maryland, USA

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 ∈ [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 < 1/2. We therefore significantly extend the area where we can do secure multiparty computation with polylogarithmic 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 dn parties are actually corrupted in a given execution, then the protocol will not abort. Our result is solely of theoretical interest. In its current form, it has not practical implications whatsoever.

Original languageEnglish
Title of host publicationPublic-Key Cryptography – PKC 2017 - 20th IACR International Conference on Practice and Theory in Public-Key Cryptography, Proceedings
EditorsSerge Fehr
Number of pages27
Place of publicationBerlin Heidelberg
PublisherSpringer VS
Publication year2017
ISBN (print)9783662543870
ISBN (Electronic)978-3-662-54388-7
Publication statusPublished - 2017
Event20th IACR International Conference on Practice and Theory of Public-Key Cryptography, PKC 2017 - Amsterdam, Netherlands
Duration: 28 Mar 201731 Mar 2017


Conference20th IACR International Conference on Practice and Theory of Public-Key Cryptography, PKC 2017
By Amsterdam
SponsorInternational Association for Cryptologic Research (IACR)
SeriesLecture Notes in Computer Science

See relations at Aarhus University Citationformats

ID: 118501150