Eran Omri

Ran Cohen, Iftach Haitner, Eran Omri et al.

In the setting of secure multiparty computation (MPC), a set of mutually distrusting parties wish to jointly compute a function, while guaranteeing the privacy of their inputs and the correctness of the output. An MPC protocol is called \emph{fully secure} if no adversary can prevent the honest parties from obtaining their outputs. A protocol is called \emph{fair} if an adversary can prematurely abort the computation, however, only before learning any new information. We present highly efficient transformations from fair computations to fully secure computations, assuming the fraction of honest parties is constant (e.g., $1\%$ of the parties are honest). Compared to previous transformations that require linear invocations (in the number of parties) of the fair computation, our transformations require super-logarithmic, and sometimes even super-constant, such invocations. The main idea is to delegate the computation to chosen random committees that invoke the fair computation. Apart from the benefit of uplifting security, the reduction in the number of parties is also useful, since only committee members are required to work, whereas the remaining parties simply "listen" to the computation over a broadcast channel.

Iftach Haitner, Nikolaos Makriyannis, Eran Omri

A two-party coin-flipping protocol is $ε$-fair if no efficient adversary can bias the output of the honest party (who always outputs a bit, even if the other party aborts) by more than $ε$. Cleve [STOC '86] showed that $r$-round $o(1/r)$-fair coin-flipping protocols do not exist. Awerbuch, Blum, Chor, Goldwasser, and Micali[Manuscript '85] constructed a $Θ(1/\sqrt{r})$-fair coin-flipping protocol, assuming the existence of one-way functions. Moran, Naor, and Segev [Journal of Cryptology '16] constructed an $r$-round coin-flipping protocol that is $Θ(1/r)$-fair (thus matching the aforementioned lower bound of Cleve [STOC '86]), assuming the existence of oblivious transfer. The above gives rise to the intriguing question of whether oblivious transfer, or more generally ``public-key primitives,'' is required for an $o(1/\sqrt r)$-fair coin flipping protocol. We make a different progress towards answering the question by showing that, for any constant $r\in \N$, the existence of an $1/(c\cdot \sqrt{r})$-fair, $r$-round coin-flipping protocol implies the existence of an infinitely-often key-agreement protocol, where $c$ denotes some universal constant (independent of $r$). Our reduction is \emph{non} black-box and makes a novel use of the recent dichotomy for two-party protocols of Haitner, Nissim, Omri, Shaltiel, and Silbak [FOCS '18] to facilitate a two-party variant of the recent attack of Beimel, Haitner, Makriyannis, and Omri [FOCS '18] on multi-party coin-flipping protocols.

Iftach Haitner, Kobbi Nissim, Eran Omri et al.

Let $π$ be an efficient two-party protocol that given security parameter $κ$, both parties output single bits $X_κ$ and $Y_κ$, respectively. We are interested in how $(X_κ,Y_κ)$ "appears" to an efficient adversary that only views the transcript $T_κ$. We make the following contributions: $\bullet$ 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 $T_κ$, the simulator outputs a pair $(X'_κ,Y'_κ)$ such that $(X'_κ,Y'_κ,T_κ)$ is (somewhat) computationally indistinguishable from $(X_κ,Y_κ,T_κ)$. $\bullet$ 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 $T_κ$, but then choose their outputs independently from some product distribution (that is determined in poly-time from $T_κ$), - or, the protocol implies a key-agreement protocol (for infinitely many $κ$'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. $\bullet$ We use the above dichotomy to make progress on open problems on minimal cryptographic assumptions required for differentially private mechanisms for the XOR function. $\bullet$ A subsequent work of Haitner et al. uses the above dichotomy to makes progress on a longstanding open question regarding the complexity of fair two-party coin-flipping protocols.

Amos Beimel, Iftach Haitner, Nikolaos Makriyannis et al.

In his seminal work, Cleve [STOC '86] has proved that any $r$-round coin-flipping protocol can be efficiently biased by $Θ(1/r)$. This lower bound was met for the two-party case by Moran, Naor, and Segev [Journal of Cryptology '16], and the three-party case (up to a $polylog$ factor) by Haitner and Tsfadi [SICOMP '17], and was approached for $n$-party protocols when $n< loglog r$ by Buchbinder, Haitner, Levi, and Tsfadia [SODA '17]. 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, Blum, Chor, Goldwasser, and Micali [Manuscript '85]. Our main result is a tighter lower bound on the bias of coin-flipping protocols, showing that, for every constant $ε>0$, an $r^ε$-party $r$-round coin-flipping protocol can be efficiently biased by $\widetildeΩ(1/\sqrt{r})$. As far as we know, this is the first improvement of Cleve's bound, and is only $n=r^ε$ (multiplicative) far from the aforementioned upper bound of Awerbuch et al.

Ran Cohen, Iftach Haitner, Eran Omri et al.

A major challenge in the study of cryptography is characterizing the necessary and sufficient assumptions required to carry out a given cryptographic task. The focus of this work is the necessity of a broadcast channel for securely computing symmetric functionalities (where all the parties receive the same output) when one third of the parties, or more, might be corrupted. Assuming all parties are connected via a peer-to-peer network, but no broadcast channel (nor a secure setup phase) is available, we prove the following characterization: 1) A symmetric $n$-party functionality can be securely computed facing $n/3\le t<n/2$ corruptions (\ie honest majority), if and only if it is \emph{$(n-2t)$-dominated}; a functionality is $k$-dominated, if \emph{any} $k$-size subset of its input variables can be set to \emph{determine} its output. 2) Assuming the existence of one-way functions, a symmetric $n$-party functionality can be securely computed facing $t\ge n/2$ corruptions (\ie no honest majority), if and only if it is $1$-dominated and can be securely computed with broadcast. It follows that, in case a third of the parties might be corrupted, broadcast is necessary for securely computing non-dominated functionalities (in which "small" subsets of the inputs cannot determine the output), including, as interesting special cases, the Boolean XOR and coin-flipping functionalities.