Paper 2022/1526

Threshold-Optimal MPC With Friends and Foes

Nikolas Melissaris, Aarhus University
Divya Ravi, Aarhus University
Sophia Yakoubov, Aarhus University

Alon et. al (Crypto 2020) initiated the study of MPC with Friends and Foes (FaF) security, which captures the desirable property that even up to $h^{*}$ honest parties should learn nothing additional about other honest parties’ inputs, even if the $t$ corrupt parties send them extra information. Alon et. al describe two flavors of FaF security: weak FaF, where the simulated view of up to $h^{*}$ honest parties should be indistinguishable from their real view, and strong FaF, where the simulated view of the honest parties should be indistinguishable from their real view even in conjunction with the simulated / real view of the corrupt parties. They give several initial FaF constructions with guaranteed output delivery (GOD); however, they leave some open problems. Their only construction which supports the optimal corruption bounds of $2t+h^{*} < n$ (where $n$ denotes the number of parties) only offers weak FaF security and takes much more than the optimal three rounds of communication. In this paper, we describe two new constructions with GOD, both of which support $2t+h^{*} < n$. Our first construction, based on threshold FHE, is the first three-round construction that matches this optimal corruption bound (though it only offers weak FaF security). Our second construction, based on a variant of BGW, is the first such construction that offers strong FaF security (though it requires more than three rounds, as well as correlated randomness). Our final contribution is further exploration of the relationship between FaF security and similar security notions. In particular, we show that FaF security does not imply mixed adversary security (where the adversary can make $t$ active and $h^{*}$ passive corruptions), and that Best of Both Worlds security (where the adversary can make $t$ active or $t+h^{*}$ passive corruptions, but not both) is orthogonal to both FaF and mixed adversary security.

Note: Added appropriate funding acknowledgements.

Available format(s)
Cryptographic protocols
Publication info
Secure ComputationFriends and FoesGuaranteed Output DeliveryRound Complexity
Contact author(s)
nikolas @ cs au dk
divya @ cs au dk
sophia yakoubov @ cs au dk
2023-02-08: revised
2022-11-04: received
See all versions
Short URL
Creative Commons Attribution


      author = {Nikolas Melissaris and Divya Ravi and Sophia Yakoubov},
      title = {Threshold-Optimal MPC With Friends and Foes},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1526},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.