Paper 2023/1605

Three Party Secure Computation with Friends and Foes

Bar Alon, Ben-Gurion University of the Negev
Amos Beimel, Ben-Gurion University of the Negev
Eran Omri, Ariel University
Abstract

In secure multiparty computation (MPC), the goal is to allow a set of mutually distrustful parties to compute some function of their private inputs in a way that preserves security properties, even in the face of adversarial behavior by some of the parties. However, classical security definitions do not pose any privacy restrictions on the view of honest parties. Thus, if an attacker adversarially leaks private information to honest parties, it does not count as a violation of privacy. This is arguably undesirable, and in real-life scenarios, it is hard to imagine that possible users would agree to have their private information revealed, even if only to other honest parties. To address this issue, Alon et al. [CRYPTO 20] introduced the notion of security with friends and foes (FaF security). In essence, $(t,h)$-FaF security requires that a malicious adversary corrupting up to $t$ parties cannot help a coalition of $h$ semi-honest parties to learn anything beyond what they can learn from their inputs and outputs (combined with the input and outputs of the malicious parties). They further showed that $(t,h)$-FaF security with $n$ parties is achievable for any functionality if $2t+h<n$, and for some functionality, $(t,h)$-FaF security is impossible assuming $2t+h\geq n$. A remaining important open problem is to characterize the set of $n$-party functionalities that can be computed with $(t,h)$-FaF security assuming $2t+h\geq n$. In this paper, we focus on the special, yet already challenging, case of $(1,1)$-FaF security for three-party, 2-ary (two inputs), symmetric (all parties output the same value) functionalities. We provide several positive results, a lower bound on the round complexity, and an impossibility result. In particular, we prove the following. (1) we identify a large class of three-party Boolean symmetric 2-ary functionalities that can be computed with $(1,1)$-FaF full security, and (2) We identify a large class of three-party (possibly non-Boolean) symmetric 2-ary functionalities, for which no $O(\log\kappa)$-round protocol computes them with $(1,1)$-FaF full security. This matches the round complexity of our positive results for various interesting functionalities, such as equality of strings.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint.
Keywords
MPC with friends and foesfull securitylower boundsprotocols
Contact author(s)
alonbar08 @ gmail com
amos beimel @ gmail com
omrier @ ariel ac il
History
2023-10-19: approved
2023-10-17: received
See all versions
Short URL
https://ia.cr/2023/1605
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2023/1605,
      author = {Bar Alon and Amos Beimel and Eran Omri},
      title = {Three Party Secure Computation with Friends and Foes},
      howpublished = {Cryptology {ePrint} Archive, Paper 2023/1605},
      year = {2023},
      url = {https://eprint.iacr.org/2023/1605}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.