Paper 2020/701

MPC with Friends and Foes

Bar Alon, Eran Omri, and Anat Paskin-Cherniavsky

Abstract

Classical definitions for secure multiparty computation assume the existence of a single adversarial entity controlling the set of corrupted parties. Intuitively, the definition requires that the view of the adversary, corrupting $t$ parties, in a real-world execution can be simulated by an adversary in an ideal model, where parties interact only via a trusted-party. No restrictions, however, are imposed on the view of honest parties in the protocol, thus, if honest parties obtain information about the private inputs of other honest parties -- it is not counted as a violation of privacy. This is arguably undesirable in many situations that fall into the MPC framework. Nevertheless, there are secure protocols (e.g., the 2-round multiparty protocol of Ishai et al.~[CRYPTO 2010] tolerating a single corrupted party) that instruct the honest parties to reveal their private inputs to all other honest parties (once the malicious party is somehow identified). In this paper, we put forth a new security notion, which we call \textit{FaF-security}, extending the classical notion. In essence, $(t,h^*)$-FaF-security requires the view of a subset of up to $h^*$ honest parties to also be simulatable in the ideal model (in addition to the view of the malicious adversary, corrupting up to $t$ parties). This property should still hold, even if the adversary leaks information to honest parties by sending them non-prescribed messages. We provide a thorough exploration of the new notion, investigating it in relation to a variety of existing security notions. We further investigate the feasibility of achieving FaF-security and show that every functionality can be computed with (computational) $(t,h^*)$-FaF full-security, if and only if $2t+ h^*<m$. Interestingly, the lower-bound result actually shows that even fair FaF-security is impossible in general when $2t+ h^*\ge m$ (surprisingly, the view of the malicious attacker is not used as the trigger for the attack). We also investigate the optimal round complexity for $(t,h^*)$-FaF-secure protocols and give evidence that the leakage of private inputs of honest parties in the protocol of Ishai et al.~[CRYPTO 2010] is inherent. Finally, we investigate the feasibility of statistical/perfect FaF-security, employing the viewpoint used by Fitzi et al.~[ASIACRYPT 1999] for \textit{mixed-adversaries}.