Secure Multi-Party Computation (MPC) allows a set of « n » distrusting parties to compute functions on their private inputs while guaranteeing secrecy of inputs while ensuring correctness of the computation. Most MPC protocols can achieve such security only against a minority of corrupted parties (e.g., there is an honest majority > n/2). Based on
cryptographic assumptions, security against dishonest majorities can be obtained but requires more computation and communication. These levels of security are often not sufficient in real life especially threats that require long-term security against powerful persistent attackers (e.g., so called Advanced Persistent Threats). In such cases, all the
parties involved in the protocol may become corrupted at some point. Proactive MPC (PMPC) aims to address such mobile persistent threats; PMPC guarantees privacy and correctness against an adversary allowed to change the set of corrupted parties over time but that is bounded by a threshold at any given instant. Until recently, PMPC protocols existed
only against a dishonest minority. The first generic PMPC protocol against a dishonest majority was introduced in a recent work to be presented in September 2018, it presents a feasibility result demonstrating that it can be achieved but with high communication complexity: O(n^4).
This talk presents our most recent work which develops an efficient generic PMPC protocol secure against a dishonest majority. We improve the overall complexity of the generic PMPC from O(n^4) to O(n^2) communication. Two necessary stepping stones for generic PMPC are Proactive Secret Sharing (PSS) and a secure distributed multiplication protocol. In this work we introduce a new PSS scheme requiring only O(n^2) communications. We also present a multiplication protocol against dishonest majorities in the proactive setting; this protocol introduces a new efficient way to perform multiplication in dishonest majority without using pre-computation.