[Resource Topic] 2021/1163: Information-Theoretically Secure MPC against Mixed Dynamic Adversaries

Welcome to the resource topic for 2021/1163

Information-Theoretically Secure MPC against Mixed Dynamic Adversaries

Authors: Ivan Damgård, Daniel Escudero, Divya Ravi


In this work we consider information-theoretically secure MPC against a mixed adversary who can corrupt t_p parties passively, t_a parties actively, and can make t_f parties fail-stop. With perfect security, it is known that every function can be computed securely if and only if 3t_a + 2t_p + t_f < n, and for statistical security the bound is 2t_a + 2t_p + t_f < n. These results say that for each given set of parameters (t_a, t_p, t_f) respecting the inequality, there exists a protocol secure against this particular choice of corruption thresholds. In this work we consider a dynamic adversary. Here, the goal is a single protocol that is secure, no matter which set of corruption thresholds (t_a, t_p, t_f) from a certain class is chosen by the adversary. A dynamic adversary can choose a corruption strategy after seeing the protocol and so is much stronger than a standard adversary. Dynamically secure protocols have been considered before for computational security. Also the information theoretic case has been studied, but only considering non-threshold general adversaries, leading to inefficient protocols. We consider threshold dynamic adversaries and information theoretic security. For statistical security we show that efficient dynamic secure function evaluation (SFE) is possible if and only if 2t_a + 2t_p + t_f < n, but any dynamically secure protocol must use \Omega(n) rounds, even if only fairness is required. Further, general reactive MPC is possible if we assume in addition that 2t_a+2t_f \leq n, but fair reactive MPC only requires 2t_a + 2t_p + t_f < n. For perfect security we show that both dynamic SFE and verifiable secret sharing (VSS) are impossible if we only assume 3t_a + 2t_p + t_f < n and remain impossible even if we also assume t_f=0. On the other hand, perfect dynamic SFE with guaranteed output delivery (G.O.D.) is possible when either t_p = 0 or t_a = 0 i.e. if instead we assume 3t_a+t_f < n or 2t_p +t_f < n. Further, perfect dynamic VSS with G.O.D. is possible under the additional conditions 3t_a + 3/2t_f \leq n or 2t_p + 2t_f \leq n. These conditions are also sufficient for dynamic perfect reactive MPC.

ePrint: https://eprint.iacr.org/2021/1163

Talk: https://www.youtube.com/watch?v=r7hHXet7J88

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .