Garbled circuits are a powerful and important cryptographic primitive, introduced by Yao [FOCS 1986] for secure two-party computation. Beaver, Micali and Rogaway (BMR) [STOCS 1990] extended the garbled circuit technique to construct the first constant-round secure multiparty computation (MPC) protocol. In the BMR protocol, the garbled circuit size grows linearly and the online computation time grows quadratically with the number of parties. Previous solutions to avoid this relied on key-homomorphic PRFs, incurring a large garbled circuit size and slow online computation time.

Private set intersection (PSI) protocols allow a set of mutually distrustful parties, each holding a private set of items, to compute the intersection over all their sets, such that no other information is revealed. PSI has a wide variety of applications including online advertising (e.g., efficacy computation), security (e.g., botnet detection, intrusion detection), proximity testing (e.g., COVID-19 contact tracing), and more. Private set intersection is a rapidly developing area and there exist many highly efficient protocols. However, almost all of these protocols are for the case of two parties or for semi-honest security. In particular, despite the high interest in this problem, prior to our work there has been no concretely efficient, maliciously secure multiparty PSI protocol.

In his seminal work, Cleve [ Proceedings of the 18th Annual ACM Symposium on Theory of Computing, 1986, pp. 364--369] has proved that any $r$-round coin-flipping protocol can be efficiently biased by $\Theta(1/r)$. This lower bound was met for the two-party case by Moran, Naor, and Segev [ J. Cryptology, 29 (2016), pp. 491--513] and the three-party case (up to a ${polylog}$ factor) by Haitner and Tsfadia [ SIAM J. Comput., 46 (2017), pp. 479--542] and was approached for $n$-party protocols when $n< {loglog} r$ by Buchbinder et al. [ Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms, 2017, pp. 2580--2600]. For $n > {loglog} r$, however, the best bias for $n$-party coin-flipping protocols remains $O(n/\sqrt{r})$ achieved by the majority protocol of Awerbuch et al. [ How to implement Bracha's ${O}(\log n)$ Byzantine Agreement Algorithm, manuscript, 1985]. Our main result is a tighter lower bound on the bias of coin-flipping protocols, showing that, for every constant $\varepsilon >0$, an $r^{\varepsilon}$-party $r$-round coin-flipping protocol can be efficiently biased by $\widetilde{\Omega}(1/\sqrt{r})$. As far as we know, this is the first improvement of Cleve's bound and is only $n=r^{\varepsilon}$ (multiplicative) far from the aforementioned upper bound of Awerbuch et al. We prove the above bound using two new results that we believe are of independent interest. The first result is that a sequence of (``augmented'') weak martingales have large gap: with constant probability there exists two adjacent variables whose gap is at least the ratio between the gap between the first and last variables and the square root of the number of variables. This generalizes over the result of Cleve and Impagliazzo [ Martingales, Collective Coin Flipping and Discrete Control Processes (Extended Abstract), http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.51.1797, 1993], who showed that the above holds for strong martingales, and allows in some setting to exploit this gap by efficient algorithms. We prove the above using a novel argument that does not follow the more complicated approach of R. Cleve and R. Impagliazzo. The second result is a new sampling algorithm that uses a differentially private mechanism to minimize the effect of data divergence.

Let $\pi$ be an efficient two-party protocol that, given security parameter $\kappa$, both parties output single bits $X_\kappa$ and $Y_\kappa$, respectively. We are interested in how $(X_\kappa,Y_\kappa)$ “appears” to an efficient adversary that only views the transcript $T_\kappa$. We make the following contributions: (a) We develop new tools to argue about this loose notion and show (modulo some caveats) that for every such protocol $\pi$, there exists an efficient simulator such that the following holds: on input $T_\kappa$, the simulator outputs a pair $(X'_\kappa,Y'_\kappa)$ such that $(X'_\kappa,Y'_\kappa,T_\kappa)$ is (somewhat) computationally indistinguishable from $(X_\kappa,Y_\kappa,T_\kappa)$. (b) We use these tools to prove the following dichotomy theorem: every such protocol $\pi$ is either uncorrelated---it is (somewhat) indistinguishable from an efficient protocol whose parties interact to produce $T_\kappa$, but then choose their outputs independently from some product distribution (that is determined in poly-time from $T_\kappa$), or the protocol implies a key-agreement protocol (for infinitely many $\kappa$'s). Uncorrelated protocols are uninteresting from a cryptographic viewpoint, as the correlation between outputs is (computationally) trivial. Our dichotomy shows that every protocol is either completely uninteresting or implies key-agreement. (c) We use the above dichotomy to make progress on open problems on minimal cryptographic assumptions required for differentially private mechanisms for the XOR function. (d) A subsequent work [I. Haitner, N. Makriyannis, and E. Omri, in Theory of Cryptography Conference, Springer, Cham, Switzerland, 2018, pp. 539--562] uses the above dichotomy to makes progress on a long-standing open question regarding the complexity of fair two-party coin-flipping protocols. We also highlight the following two ideas regarding our technique: (a) The simulator algorithm is obtained by a carefully designed “competition” between efficient algorithms attempting to forecast $(X_\kappa,Y_\kappa)|_{T_\kappa=t}$. The winner is used to simulate the outputs of the protocol. (b) Our key-agreement protocol uses the simulation to reduce to an information theoretic setup and is, in some sense, a non-black-box.

In his seminal work, Cleve [STOC '86] proved that the bias of any coin-flipping protocol is inversely proportional to the number of rounds. This lower bound was met for the two-party case by Moran et al. [Journal of Cryptology '16], and the three-party case (up to a polylogarithmic factor) by Haitner and Tsfadia [SICOMP '17], and was approached for multi-party protocols by Haitner et al. [SODA '17] when the number of rounds is at least doubly exponential in the number of parties. For the complement case, however, the best bias for multi-party coin-flipping protocols is proportional to the number of parties and inversely proportional to the square root of the number of rounds. The latter bias is achieved by the majority protocol of Awerbuch et al. [Manuscript '85]. Our main result is a tighter lower bound on the bias of coin-flipping protocols, showing that, if the number of rounds is bounded by some polynomial in the number of parties, then the bias is lower-bounded by a quantity that is inversely proportional to the square root of the number of rounds (up to a polylogarithmic factor). As far as we know, this is the first improvement of Cleve's bound, and is far from the aforementioned upper bound of Awerbuch et al. only by a factor of the number of parties. We prove the above bound using two new results that we believe are of independent interest. The first result is that a sequence of ("augmented") weak martingales have large gap: with constant probability there exists two adjacent variables whose gap is at least the ratio between the gap between the first and last variables and the square root of the number of variables. This generalizes over the result of Cleve and Impagliazzo [Manuscript '93], who showed that the above holds for strong martingales, and allows in some setting to exploit this gap by efficient algorithms. We prove the above using a novel argument that does not follow the more complicated approach of Cleve and Impagliazzo. The second result is a new sampling algorithm that uses a differentially private mechanism to minimize the effect of data divergence.

Let π be an efficient two-party protocol that given security parameter k, both parties output single bits Xkand Yk, respectively. We are interested in how (Xk, Yk) "appears" to an efficient adversary that only views the transcript Tk. We make the following contributions: · We develop new tools to argue about this loose notion, and show (modulo some caveats) that for every such protocol π, there exists an efficient simulator such that the following holds: on input Tk, the simulator outputs a pair (X'k, Y'k) such that (X'k, Y'k, Tk) is (somewhat) computationally indistinguishable from (Xk, Yk, Tk). · We use these tools to prove the following dichotomy theorem: every such protocol π is: - either uncorrelated - it is (somewhat) indistinguishable from an efficient protocol whose parties interact to produce Tk, but then choose their outputs independently from some product distribution (that is determined in poly-time from Tk), - or, the protocol implies a key-agreement protocol (for infinitely many k's). Uncorrelated protocols are uninteresting from a cryptographic viewpoint, as the correlation between outputs is (computationally) trivial. Our dichotomy shows that every protocol is either completely uninteresting or implies key-agreement. ·We use the above dichotomy to make progress on open problems on minimal cryptographic assumptions required for differentially private mechanisms for the XOR function. · A subsequent work of Haitner et al. uses the above dichotomy to makes progress on a long-standing open question regarding the complexity of fair two-party coin-flipping protocols. We highlight the following ideas regarding our technique: · The simulator algorithm is obtained by a carefully designed "competition" between efficient algorithms attempting to forecast ((Xk, Yk)|Tk= t). The winner is used to simulate the outputs of the protocol. · Our key-agreement protocol uses the simulation to reduce to an information theoretic setup, and is in some sense non-black box.

In the setting of secure multiparty computation, a set of parties with private inputs wish to compute some function of their inputs without revealing anything but their output. Over the last decade, the efficiency of secure two-party computation has advanced in leaps and bounds, with speedups of some orders of magnitude, making it fast enough to be of use in practice. In contrast, progress on the case of multiparty computation (with more than two parties) has been much slower, with very little work being done. Currently, the only implemented efficient multiparty protocol has many rounds of communication (linear in the depth of the circuit being computed) and thus is not suited for Internet-like settings where latency is not very low. In this paper, we construct highly efficient constant-round protocols for the setting of multiparty computation for semi-honest adversaries. Our protocols work by constructing a multiparty garbled circuit, as proposed in BMR (Beaver et al., STOC 1990). Our first protocol uses oblivious transfer and constitutes the first concretely-efficient constant-round multiparty protocol for the case of no honest majority. Our second protocol uses BGW, and is significantly more efficient than the FairplayMP protocol (Ben-David et al., CCS 2008) that also uses BGW.

It is well known (cf. Impagliazzo and Luby [in Proceedings of the 30th Annual IEEE Symposium on Foundations of Computer Science, 1989, pp. 230--235]) that the existence of almost all “interesting" cryptographic applications, i.e., ones that cannot hold information theoretically, implies one-way functions. An important exception where the above implication is not known, however, is the case of coin-flipping protocols. Such protocols allow honest parties to mutually flip an unbiased coin, while guaranteeing that even a cheating (efficient) party cannot bias the output of the protocol by much. Impagliazzo and Luby proved that coin-flipping protocols that are safe against negligible bias do imply one-way functions, and, very recently, Maji, Prabhakaran, and Sahai [in Proceedings of the 2001 51st Annual IEEE Symposium on Foundations of Computer Science, 2010, pp. 613--622] proved the same for constant-round protocols (with any nontrivial bias). For the general case, however, no such implication was known. We make progress towards answering the above fundamental question, showing that (strong) coin-flipping protocols safe against a constant bias (concretely, $\frac{\sqrt2 -1}2 - o(1)$) imply one-way functions.

It is well known (cf., Impagliazzo and Luby [FOCS '89]) that the existence of almost all "interesting" cryptographic applications, i.e., ones that cannot hold information theoretically, implies one-way functions. An important exception where the above implication is not known, however, is the case of coin-flipping protocols. Such protocols allow honest parties to mutually flip an unbiased coin, while guaranteeing that even a cheating (efficient) party cannot bias the output of the protocol by much. Impagliazzo and Luby proved that coin-flipping protocols that are safe against negligible bias do imply one-way functions, and, very recently, Maji, Prabhakaran, and Sahai [FOCS '10] proved the same for constant-round protocols (with any non-trivial bias). For the general case, however, no such implication was known. We make progress towards answering the above fundamental question, showing that (strong) coin-flipping protocols safe against a constant bias (concretely, (√2 -1)/2 - o(1)) imply one-way functions.