Paper 2023/1608

Can Alice and Bob Guarantee Output to Carol?

Bar Alon, Ben-Gurion University of the Negev
Eran Omri, Ariel University
Muthuramakrishnan Venkitasubramaniam, Georgetown University

In the setting of solitary output computations, only a single designated party learns the output of some function applied to the private inputs of all participating parties with the guarantee that nothing beyond the output is revealed. The setting of solitary output functionalities is a special case of secure multiparty computation, which allows a set of mutually distrusting parties to compute some function of their private inputs. The computation should guarantee some security properties, such as correctness, privacy, fairness, and output delivery. Full security captures all these properties together. Solitary output computation is a common setting that has become increasingly important, as it is relevant to many real-world scenarios, such as federated learning and set disjointness. In the set-disjointness problem, a set of parties with private datasets wish to convey to another party whether they have a common input. In this work, we investigate the limits of achieving set-disjointness which already has numerous applications and whose feasibility (under non-trivial conditions) was left open in the work of Halevi et al. (TCC 2019). Towards resolving this, we completely characterize the set of Boolean functions that can be computed in the three-party setting in the face of a malicious adversary that corrupts up to two of the parties. As a corollary, we characterize the family of set-disjointness functions that can be computed in this setting, providing somewhat surprising results regarding this family and resolving the open question posed by Halevi et al.

Available format(s)
Cryptographic protocols
Publication info
solitary outputfull securityimpossibility resultsprotocols
Contact author(s)
alonbar08 @ gmail com
omrier @ ariel ac il
mv783 @ georgetown edu
2023-10-19: approved
2023-10-17: received
See all versions
Short URL
Creative Commons Attribution


      author = {Bar Alon and Eran Omri and Muthuramakrishnan Venkitasubramaniam},
      title = {Can Alice and Bob Guarantee Output to Carol?},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1608},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.