International Association
for Cryptologic Research

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.

In the current digital world, large organizations (sometimes referred to as tech giants) provide service to extremely large numbers of users. The service provider is often interested in computing various data analyses over the private data of its users, which in turn have their incentives to cooperate, but do not necessarily trust the service provider. In this work, we introduce the \emph{Gulliver multi-party computation model} (GMPC) to realistically capture the above scenario. The GMPC model considers a single highly powerful party, called the {\em server} or {\em Gulliver}, that is connected to $n$ users over a star topology network (alternatively formulated as a full network, where the server can block any message). The users are significantly less powerful than the server, and, in particular, should have both computation and communication complexities that are polylogarithmic in $n$. Protocols in the GMPC model should be secure against malicious adversaries that may corrupt a subset of the users and/or the server. Designing protocols in the GMPC model is a delicate task, since users can only hold information about $\polylog(n)$ other users (and, in particular, can only communicate with $\polylog(n)$ other users). In addition, the server can block any message between any pair of honest parties. Thus, reaching an agreement becomes a challenging task. Nevertheless, we design generic protocols in the GMPC model, assuming that at most $\alpha<1/8$ fraction of the users may be corrupted (in addition to the server). Our main contribution is a variant of Feige's committee election protocol [FOCS 1999] that is secure in the GMPC model. Given this tool we show: 1. Assuming fully homomorphic encryption (FHE), any computationally efficient function with $O(n\cdot\polylog(n))$-size output can be securely computed in the GMPC model. 2. Any function that can be computed by a circuit of $O(\polylog(n))$ depth, $O(n\cdot\polylog(n))$ size, and bounded fan-in and fan-out can be securely computed in the GMPC model assuming vector commitment schemes (without assuming FHE). 3. In particular, {\em sorting} can be securely computed in the GMPC model assuming vector commitment schemes. This has important applications for the {\em shuffle model of differential privacy}, and resolves an open question of Bell et al. [CCS 2020].

Evolving secret-sharing schemes, defined by Komargodski, Naor, and Yogev [TCC 2016B], are secret-sharing schemes in which there is no a-priory bound on the number of parties. In such schemes, parties arrive one by one; when a party arrives, the dealer gives it a share and cannot update this share in later stages. The requirement is that some predefined sets (called authorized sets) should be able to reconstruct the secret, while other sets should learn no information on the secret. The collection of authorized sets that can reconstruct the secret is called an evolving access structure. The challenge of the dealer is to be able to give short shares to the current parties without knowing how many parties will arrive in the future. The requirement that the dealer cannot update shares is designed to prevent expensive updates. Komargodski et al. constructed an evolving secret-sharing scheme for every monotone evolving access structure; the share size of the t-th party in this scheme is $2^{t-1}$. Recently, Mazor [ITC 2023] proved that evolving secret-sharing schemes require exponentially-long shares for some evolving access structures, namely shares of size $2^{t-o(t)}$. In light of these results, our goal is to construct evolving secret-sharing schemes with non-trivial share size for wide classes of evolving access structures; e.g., schemes with share size $2^{ct}$ for $c<1$ or even polynomial size. We provide several results achieving this goal: (1) We define layered infinite branching programs representing evolving access structures, show how to transform them into generalized infinite decision trees, and show how to construct evolving secret-sharing schemes for generalized infinite decision trees. Combining these steps, we get a secret-sharing scheme realizing the evolving access structure. As an application of this framework, we construct an evolving secret-sharing scheme with non-trivial share size for access structures that can be represented by layered infinite branching programs with width at layer $t$ of at most $2^{0.15t}$. If the width is polynomial, then we get an evolving secret-sharing scheme with quasi-polynomial share size. (2) We construct efficient evolving secret-sharing schemes for dynamic-threshold access structures with high dynamic-threshold and for infinite 2-slice and 3-slice access structures. (3) We prove lower bounds on the share size of evolving secret-sharing schemes for infinite $k$-hypergraph access structures and for infinite directed st-connectivity access structures. As a by-product of the lower bounds, we provide the first non-trivial lower bound for \emph{finite} directed st-connectivity access structures for general secret-sharing schemes.

Fully secure multiparty computation (MPC) allows a set of parties to compute some function of their inputs, while guaranteeing correctness, privacy, fairness, and output delivery. Understanding the necessary and sufficient assumptions that allow for fully secure MPC is an important goal. Cleve (STOC’86) showed that full security cannot be obtained in general without an honest majority. Conversely, by Rabin and Ben-Or (STOC’89), assuming a broadcast channel and an honest majority enables a fully secure computation of any function. Our goal is to characterize the set of functionalities that can be computed with full security, assuming an honest majority, but no broadcast. This question was fully answered by Cohen et al. (TCC’16)—for the restricted class of symmetric functionalities (where all parties receive the same output). Instructively, their results crucially rely on agreement and do not carry over to general asymmetric functionalities. In this work, we focus on the case of three-party asymmetric functionalities, providing a variety of necessary and sufficient conditions to enable fully secure computation. An interesting use-case of our results is server-aided computation, where an untrusted server helps two parties to carry out their computation. We show that without a broadcast assumption, the resource of an external non-colluding server provides no additional power. Namely, a functionality can be computed with the help of the server if and only if it can be computed without it. For fair coin tossing, we further show that the optimal bias for three-party (server-aided) r -round protocol remains $$\Theta \left( 1/r\right) $$ Θ 1 / r (as in the two-party setting).

An $$\alpha $$ α -fair coin-tossing protocol allows a set of mutually distrustful parties to generate a uniform bit, such that no efficient adversary can bias the output bit by more than $$\alpha $$ α . Cleve (in: Proceedings of the 18th annual ACM symposium on theory of computing (STOC), 1986) has shown that if half of the parties can be corrupted, then no $$r$$ r -round coin-tossing protocol is $$o(1/r)$$ o ( 1 / r ) -fair. For over two decades, the best-known m -party protocols, tolerating up to $${t}\ge m/2$$ t ≥ m / 2 corrupted parties, were only $$O\left( {t}/\sqrt{r} \right) $$ O t / r -fair. In a surprising result, Moran et al. (in: Theory of cryptography, sixth theory of cryptography conference, TCC, 2009) constructed an $$r$$ r -round two-party $$O(1/r)$$ O ( 1 / r ) -fair coin-tossing protocol, i.e., an optimally fair protocol. Beimel et al. (in: Rabin (ed) Advances in cryptology—CRYPTO 2010, volume 6223 of lecture notes in computer science, Springer, 2010) extended the result of Moran et al. to the multiparty setting where strictly fewer than 2/3 of the parties are corrupted. They constructed a $$2^{2^k}/r$$ 2 2 k / r -fair r -round m -party protocol, tolerating up to $$t=\frac{m+k}{2}$$ t = m + k 2 corrupted parties. In a breakthrough result, Haitner and Tsfadia (in: Symposium on theory of computing, STOC, 2014) constructed an $$O\left( \log ^3(r)/r \right) $$ O log 3 ( r ) / r -fair (almost optimal) three-party coin-tossing protocol. Their work brought forth a combination of novel techniques for coping with the difficulties of constructing fair coin-tossing protocols. Still, the best coin-tossing protocols for the case where more than 2/3 of the parties may be corrupted (and even when $$t=2m/3$$ t = 2 m / 3 , where $$m>3$$ m > 3 ) were $$\theta \left( 1/\sqrt{r} \right) $$ θ 1 / r -fair. We construct an $$O\left( \log ^3(r)/r \right) $$ O log 3 ( r ) / r -fair m -party coin-tossing protocol, tolerating up to t corrupted parties, whenever m is constant and $$t<3m/4$$ t < 3 m / 4 .

Solitary output secure computation models scenarios, where a single entity wishes to compute a function over an input that is distributed among several mutually distrusting parties. The computation should guarantee some security properties, such as correctness, privacy, and guaranteed output delivery. Full security captures all these properties together. This setting is becoming very important, as it is relevant to many real-world scenarios, such as service providers wishing to learn some statistics on the private data of their users. In this paper, we study full security for solitary output three-party functionalities in the point-to-point model (without broadcast) assuming at most a single party is corrupted. We give a characterization of the set of three-party Boolean functionalities and functionalities with up to three possible outputs (over a polynomial-size domain) that are computable with full security in the point-to-point model against a single corrupted party. We also characterize the set of three-party functionalities (over a polynomial-size domain) where the output receiving party has no input. Using this characterization, we identify the set of parameters that allow certain functionalities related to private set intersection to be securely computable in this model. Our characterization in particular implies that, even in the solitary output setting, without broadcast not many ``interesting'' three-party functionalities can be computed with full security. Our main technical contribution is a reinterpretation of the hexagon argument due to Fischer et al. [Distributed Computing '86]. While the original argument relies on the agreement property (i.e., all parties output the same value) to construct an attack, we extend the argument to the solitary output setting, where there is no agreement. Furthermore, using our techniques, we were also able to advance our understanding of the set of solitary output three-party functionalities that can be computed with full security, assuming broadcast but where two parties may be corrupted. Specifically, we extend the set of such functionalities that were known to be computable, due to Halevi et al. [TCC '19].

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 some 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 \emph{honest} parties, it does not count as a violation of privacy. Moreover, even the protocol itself may instruct all parties to send their inputs to other honest parties (if, say, all corrupted parties have been previously revealed). 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 \emph{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 full security with $n$ parties is achievable for any functionality if and only if $2t+h<n$. A remaining important open problem is to characterize the set of $n$-party functionalities that can be computed with $(t,h)$-FaF full security assuming $2t+h\geq n$. In this paper, we focus on the special, yet already challenging, case of $(1,1)$-FaF full 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. 2. We identify a large class of three-party (possibly non-Boolean) symmetric 2-ary functionalities, for which no $O(\log\secParam)$-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.

A multi-party computation protocol is {\em perfectly secure} for some function $f$ if it perfectly emulates an ideal computation of $f$. Thus, perfect security is the strongest and most desirable notion of security, as it guarantees security in the face of any adversary and eliminates the dependency on any security parameter. Ben-Or et al. [STOC '88] and Chaum et al. [STOC '88] showed that any function can be computed with perfect security if strictly less than one-third of the parties can be corrupted. For two-party sender-receiver functionalities (where only one party receives an output), Ishai et al. [TCC '13] showed that any function can be computed in the correlated randomness model. Unfortunately, they also showed that perfect security cannot be achieved in general for two-party functions that give outputs to both parties (even in the correlated randomness model). We study the feasibility of obtaining perfect security for deterministic symmetric two-party functionalities (i.e., where both parties obtain the same output) in the face of malicious adversaries. We explore both the plain model as well as the correlated randomness model. We provide positive results in the plain model, and negative results in the correlated randomness model. As a corollary, we obtain the following results. \begin{enumerate} \item We provide a characterization of symmetric functionalities with (up to) four possible outputs that can be computed with perfect security. The characterization is further refined when restricted to three possible outputs and to Boolean functions. All characterizations are the same for both the plain model and the correlated randomness model. \item We show that if a functionality contains an embedded XOR or an embedded AND, then it cannot be computed with perfect security (even in the correlated randomness model). \end{enumerate}

A recent result by Dulek et al. (EUROCRYPT 2020) showed a secure protocol for computing any quantum circuit even without the presence of an honest majority. Their protocol, however, is susceptible to a ``denial of service'' attack and allows even a single corrupted party to force an abort. We propose the first quantum protocol that admits security-with-identifiable-abort, which allows the honest parties to agree on the identity of a corrupted party in case of an abort. Additionally, our protocol is the first to have the property that the number of rounds where quantum communication is required is independent of the circuit complexity. Furthermore, if there exists a post-quantum secure classical protocol whose round complexity is independent of the circuit complexity, then our protocol has this property as well. Our protocol is secure under the assumption that classical quantum-resistant fully homomorphic encryption schemes with decryption circuit of logarithmic depth exist. Interestingly, our construction also admits a reduction from quantum fair secure computation to classical fair secure computation.

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 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.

Fully secure multiparty computation (MPC) allows a set of parties to compute some function of their inputs, while guaranteeing correctness, privacy, fairness, and output delivery. Understanding the necessary and sufficient assumptions that allow for fully secure MPC is an important goal. Cleve (STOC'86) showed that full security cannot be obtained in general without an honest majority. Conversely, by Rabin and Ben-Or (FOCS'89), assuming a broadcast channel and an honest majority, any function can be computed with full security. Our goal is to characterize the set of functionalities that can be computed with full security, assuming an honest majority, but no broadcast. This question was fully answered by Cohen et al. (TCC'16) -- for the restricted class of \emph{symmetric} functionalities (where all parties receive the same output). Instructively, their results crucially rely on \emph{agreement} and do not carry over to general \emph{asymmetric} functionalities. In this work, we focus on the case of three-party asymmetric functionalities, providing a variety of necessary and sufficient conditions to enable fully secure computation. An interesting use-case of our results is \emph{server-aided} computation, where an untrusted server helps two parties to carry out their computation. We show that without a broadcast assumption, the resource of an external non-colluding server provides no additional power. Namely, a functionality can be computed with the help of the server if and only if it can be computed without it. For fair coin tossing, we further show that the optimal bias for three-party (server-aided) $r$-round protocol remains $\Theta(1/r)$ (as in the two-party setting).

A well known result by Kilian [22] (ACM 1988) asserts that general secure two computation (2PC) with statistical security, can be based on OT. Specifically, in the client-server model, where only one party – the client – receives an output, Kilian’s result shows that given the ability to call an ideal oracle that computes OT, two parties can securely compute an arbitrary function of their inputs with unconditional security. Ishai et al. [19] (EUROCRYPT 2011) further showed that this can be done efficiently for every two-party functionality in $$\mathrm {NC}^1$$ in a single round.However, their results only achieve statistical security, namely, it is allowed to have some error in security. This leaves open the natural question as to which client-server functionalities can be computed with perfect security in the OT-hybrid model, and what is the round complexity of such computation. So far, only a handful of functionalities were known to have such protocols. In addition to the obvious theoretical appeal of the question towards better understanding secure computation, perfect, as opposed to statistical reductions, may be useful for designing secure multiparty protocols with high concrete efficiency, achieved by eliminating the dependence on a security parameter.In this work, we identify a large class of client-server functionalities $$f:\mathcal {X}\times \mathcal {Y}\mapsto \{0,1\}$$, where the server’s domain $$\mathcal {X}$$ is larger than the client’s domain $$\mathcal {Y}$$, that have a perfect reduction to OT. Furthermore, our reduction is 1-round using an oracle to secure evaluation of many parallel invocations of $$\left( {\begin{array}{c}2\\ 1\end{array}}\right) \text {-bit-OT}$$, as done by Ishai et al. [19] (EUROCRYPT 2011). Interestingly, the set of functions that we are able to compute was previously identified by Asharov [2] (TCC 2014) in the context of fairness in two-party computation, naming these functions full-dimensional. Our result also extends to randomized non-Boolean functions $$f: \mathcal {X}\times \mathcal {Y}\mapsto \left\{ 0,\ldots ,k-1\right\} $$ satisfying $$|\mathcal {X}|>(k-1)\cdot |\mathcal {Y}|$$.