Paper 2021/1163

Information-Theoretically Secure MPC against Mixed Dynamic Adversaries

Ivan Damgård, Daniel Escudero, and 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.

Available format(s)
Cryptographic protocols
Publication info
A major revision of an IACR publication in TCC 2021
Information-theoretic securitydynamic adversarymixed corruptionfairnessguaranteed output delivery
Contact author(s)
divya 18oct @ gmail com
daniel @ escudero me
ivan @ cs au dk
2022-01-17: revised
2021-09-14: received
See all versions
Short URL
Creative Commons Attribution


      author = {Ivan Damgård and Daniel Escudero and Divya Ravi},
      title = {Information-Theoretically Secure MPC against Mixed Dynamic Adversaries},
      howpublished = {Cryptology ePrint Archive, Paper 2021/1163},
      year = {2021},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.