Threshold-Optimal MPC with Friends and Foes

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^{\ast }$ 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^{\ast }$ 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^{\ast }<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^{\ast }<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^{\ast }$ passive corruptions), and that Best of Both Worlds security (where the adversary can make $t$ active or $t+h^{\ast }$ passive corruptions, but not both) is orthogonal to both FaF and mixed adversary security.