Proactive secure multiparty computation with a dishonest majority

Karim Eldefrawy, Rafail Ostrovsky, Sunoo Park, Moti Yung

Research output: Chapter in Book/Report/Conference proceedingConference contribution


Secure multiparty computation (MPC) protocols enable n distrusting parties to perform computations on their private inputs while guaranteeing confidentiality of inputs (and outputs, if desired) and correctness of the computation, as long as no adversary corrupts more than a threshold t of the n parties. Existing MPC protocols assure perfect security for t≤ ⌈ n/ 2 ⌉ - 1 active corruptions with termination (i.e., robustness), or up to t= n- 1 under cryptographic assumptions (with detection of misbehaving parties). However, when computations involve secrets that have to remain confidential for a long time such as cryptographic keys, or when dealing with strong and persistent adversaries, such security guarantees are not enough. In these situations, all parties may be corrupted over the lifetime of the secrets used in the computation, and the threshold t may be violated over time (even as portions of the network are being repaired or cleaned up). Proactive MPC (PMPC) addresses this stronger threat model: it guarantees correctness and input privacy in the presence of a mobile adversary that controls a changing set of parties over the course of a protocol, and could corrupt all parties over the lifetime of the computation, as long as no more than t are corrupted in each time window (called a refresh period). The threshold t in PMPC represents a tradeoff between the adversary’s penetration rate and the cleaning speed of the defense tools (or rebooting of nodes from a clean image), rather than being an absolute bound on corruptions. Prior PMPC protocols only guarantee correctness and confidentiality in the presence of an honest majority of parties, an adversary that corrupts even a single additional party beyond the n/ 2 - 1 threshold, even if only passively and temporarily, can learn all the inputs and outputs; and if the corruption is active rather than passive, then the adversary can even compromise the correctness of the computation. In this paper, we present the first feasibility result for constructing a PMPC protocol secure against a dishonest majority. To this end, we develop a new PMPC protocol, robust and secure against t< n- 2 passive corruptions when there are no active corruptions, and secure but non-robust (but with identifiable aborts) against t< n/ 2 - 1 active corruptions when there are no passive corruptions. Moreover, our protocol is secure (with identifiable aborts) against mixed adversaries controlling, both, passively and actively corrupted parties, provided that if there are k active corruptions, there are less than n- k- 1 total corruptions.

Original languageEnglish (US)
Title of host publicationSecurity and Cryptography for Networks - 11th International Conference, SCN 2018, Proceedings
EditorsDario Catalano, Roberto De Prisco
PublisherSpringer Verlag
Number of pages16
ISBN (Print)9783319981123
StatePublished - 2018
Event11th International Conference on Security and Cryptography for Networks, SCN 2018 - Amalfi, Italy
Duration: Sep 5 2018Sep 7 2018

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume11035 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference11th International Conference on Security and Cryptography for Networks, SCN 2018

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Proactive secure multiparty computation with a dishonest majority'. Together they form a unique fingerprint.

Cite this