2021
Large Scale, Actively Secure Computation from LPN and FreeXOR Garbled Circuits.
Aner BenEfraim and Kelong Cong and Eran Omri and Emmanuela Orsini and Nigel P. Smart and Eduardo SoriaVazquez
EUROCRYPT 2021
Preliminary full version [eprint]
Abstarct:
We present a secure multiparty computation (MPC) protocol based on garbled circuits which is both actively secure and supports the freeXOR technique, and which has communication complexity O(n)O(n) per party. This improves on a protocol of BenEfraim, Lindell and Omri which only achieved passive security, without support for freeXOR. Our construction is based on a new variant of LPNbased encryption, but has the drawback of requiring a rather expensive garbling phase. To address this issue we present a second protocol that assumes at least n/cn/c of the parties are honest (for an arbitrary fixed value cc). This second protocol allows for a significantly lighter preprocessing, at the cost of a small sacrifice in online efficiency. We demonstrate the practicality of our evaluation phase with a implementation.
______________________________________________
PSImple: Practical Multiparty MaliciouslySecure Private Set Intersection.
Aner BenEfraim and Olga Nissenbaum and Eran Omri and Anat PaskinCherniavsky.
Manuscript
Preliminary full version [eprint]
Abstarct:
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., COVID19 contact tracing), and more. PSI 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 semihonest security. In particular, prior to our work, there has been no concretely efficient, maliciously secure multiparty PSI protocol.
We present PSImple, the first concretely efficient maliciouslysecure multiparty PSI protocol.
2020
MPC with Friends and Foes
Bar Alon and Eran Omri and Anat PaskinCherniavsky.
CRYPTO 2020
Preliminary full version [eprint]
Abstarct:
IIn their breakthrough result, Moran, Naor, and Segev [Journal of Cryptology '16] show how to construct an rroundround twoparty coinflipping with bias Θ(1/r). This improves over the Θ(1/√r)bias protocol of Awerbuch, Blum, Chor, Goldwasser, and Micali [Manuscript '85], and matches the lower bound of Cleve [STOC '86]. The protocol of Moran et. al, however, uses oblivious transfer, to be compared with the protocol of Awerbuch et. al that can be based on any oneway function. An intriguing open question is whether oblivious transfer, or more generally "publickey primitives", is required for an o(1/r)bias coin flipping. This question was partially answered in the blackbox settings by DachmanSoled et al. [11] [TCC '11] and DachmanSoled et al. [12] [TCC '14], who showed that restricted types of fully blackbox reductions cannot established such o(1/r)bias coinflipping protocol from oneway functions.
(Read more...)
______________________________________________
On the Power of an Honest Majority in ThreeParty Computation Without Broadcast
Bar Alon and Ran Cohen and Eran Omri and Tom Suad.
TCC 2020
Preliminary full version [eprint]
Abstarct:
I
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 BenOr (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.
______________________________________________
2019
On the Complexity of Fair Coin Flipping
Iftach Haitner and Nikolaos Makriyannis and Eran Omri
TCC 2018
Abstarct:
IIn their breakthrough result, Moran, Naor, and Segev [Journal of Cryptology '16] show how to construct an rroundround twoparty coinflipping with bias Θ(1/r). This improves over the Θ(1/√r)bias protocol of Awerbuch, Blum, Chor, Goldwasser, and Micali [Manuscript '85], and matches the lower bound of Cleve [STOC '86]. The protocol of Moran et. al, however, uses oblivious transfer, to be compared with the protocol of Awerbuch et. al that can be based on any oneway function. An intriguing open question is whether oblivious transfer, or more generally "publickey primitives", is required for an o(1/r)bias coin flipping. This question was partially answered in the blackbox settings by DachmanSoled et al. [11] [TCC '11] and DachmanSoled et al. [12] [TCC '14], who showed that restricted types of fully blackbox reductions cannot established such o(1/r)bias coinflipping protocol from oneway functions.
We make progress towards answering the above question, showing that for any (constant) r ∈ N, the existence of an rround o(1/r)bias coin flipping protcol implies the existence of an infinitelyoften keyagreement protocol. Our reduction is non blackbox, and makes a novel use of the recent dichotomy for twoparty protocols of Haitner et al. [ECCC '18] to facilitate, for the twoparty case, the recent attack of Beimel et al [ECCC '17] on multiparty coinflipping protocols.
______________________________________________
2018
On the Complexity of Fair Coin Flipping
Iftach Haitner and Nikolaos Makriyannis and Eran Omri
TCC 2018
Abstarct:
In their breakthrough result, Moran, Naor, and Segev [Journal of Cryptology '16] show how to construct an rroundround twoparty coinflipping with bias Θ(1/r). This improves over the Θ(1/√r)bias protocol of Awerbuch, Blum, Chor, Goldwasser, and Micali [Manuscript '85], and matches the lower bound of Cleve [STOC '86]. The protocol of Moran et. al, however, uses oblivious transfer, to be compared with the protocol of Awerbuch et. al that can be based on any oneway function. An intriguing open question is whether oblivious transfer, or more generally "publickey primitives", is required for an o(1/r)bias coin flipping. This question was partially answered in the blackbox settings by DachmanSoled et al. [11] [TCC '11] and DachmanSoled et al. [12] [TCC '14], who showed that restricted types of fully blackbox reductions cannot established such o(1/r)bias coinflipping protocol from oneway functions.
We make progress towards answering the above question, showing that for any (constant) r ∈ N, the existence of an rround o(1/r)bias coin flipping protcol implies the existence of an infinitelyoften keyagreement protocol. Our reduction is non blackbox, and makes a novel use of the recent dichotomy for twoparty protocols of Haitner et al. [ECCC '18] to facilitate, for the twoparty case, the recent attack of Beimel et al [ECCC '17] on multiparty coinflipping protocols.
______________________________________________
Computational TwoParty Correlation.
Iftach Haitner and Eran Omri and Kobbi Nissim and Ronen Shaltiel and Jad Silbak
FOCS 2018
Abstarct:
We prove a dichotomy theorem for twoparty protocols, and show that for every polytime twoparty protocol with singlebit output, at least one of following holds:

The protocol can be used to construct a keyagreement protocol.

For every constant ρ > 0 the parties' output is ρuncorrelated: let (X; Y; T) denote the parties' outputs and the protocol's transcript respectively. A protocol is ρuncorrelated if there exists an efficient "decorralizer" algorithm Decor, that when given a random transcript T, produces two numbers PA; PB, such that no efficient algorithm can distinguish (UPA ;UPB ; T) (where Updenotes a biassed coin with bias p from (X; Y; T), with distinguishing advantage larger than ρ.
Namely, if the protocol cannot be used to construct keyagreement, then its output distribution (X; Y; T) is trivial: it can be simulated noninteractively by the parties given public randomness (used to sample T). (The precise statement also has qualifiers of the form: "on infinitely many choices of the security parameter").
______________________________________________
Tighter Bounds on MultiParty Coin Flipping, via Augmented Weak Martingales and Differentially Private Sampling.
Amos Beimel and Iftach Haitner and Nikolaos Makriyannis and Eran Omri
FOCS 2018
Abstarct:
In his seminal work, Cleve [STOC 1986] has proved that any rround coinflipping protocol can be efficiently biassed by Ω(1/r). The above lower bound was met for the twoparty case by Moran, Naor, and Segev [Journal of Cryptology '16], and the threeparty case (up to a polylog factor) byHaitner and Tsfadia [SICOMP '17], and was approached for nparty protocols when n < loglog r by Buchbinder, Haitner, Levi, and Tsfadia [SODA '17]. For n > loglog r, however, the best bias for nparty coinflipping protocols remains Θ(n/√r) achieved by the majority protocol of Awerbuch, Blum, Chor, Goldwasser, and Micali [Manuscript '85].
(Read more...)
______________________________________________
Efficient Scalable Multiparty Private SetIntersection via Garbled Bloom Filters.
Roi Inbar and Eran Omri and Benny Pinkas
SCN 2018
Abstarct:
In private set intersection (PSI), a set of parties, each holding
a private data set, wish to compute the intersection over all data sets
in a manner that guarantees both correctness and privacy. This secure
computation task is of great importance and usability in many different
reallife scenarios. Much research was dedicated to the construction of
PSItailored concretely efficient protocols for the case of twoparty PSI.
The case of many parties has been given much less attention, despite
probably being a more realistic setting for most applications.
In this work, we propose a new concretely efficient, highly scalable, secure
computation protocol for multiparty PSI.
______________________________________________
From Fairness to Full Security in Multiparty Computation.
Ran Cohen and Iftach Haitner and Eran Omri and Lior Rotem
SCN 2018
Preliminary full version [eprint]
Abstarct:
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 fully secure if no adversary can prevent the honest parties from obtaining their outputs. A protocol is called 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).
______________________________________________
2017
Efficient Scalable ConstantRound MPC via Garbled Circuits.
Aner BenEfraim and Yehuda Lindell and Eran Omri
ASIACRYPT 2017
Abstarct:
In the setting of secure multiparty computation, a set of mutually distrustful parties carry out a joint computation of their inputs, without revealing anything but the output. Over recent years, there has been tremendous progress towards making secure computation practical, with great success in the twoparty case. In contrast, in the multiparty case, progress has been much slower, even for the case of semihonest adversaries.
In this paper, we consider the case of constantround multiparty computation, via the garbled circuit approach of BMR (Beaver et al., STOC 1990). In recent work, it was shown that this protocol can be efficiently instantiated for semihonest adversaries (BenEfraim et al., ACM CCS 2016). However, it scales very poorly with the number of parties, since the cost of garbled circuit evaluation is \emph{quadratic} in the number of parties, per gate...
______________________________________________
Concrete Efficiency Improvements for
Multiparty Garbling with an Honest Majority.
Aner BenEfraim and and Eran Omri
Latincrypt 2017
Abstarct:
Secure multiparty computation is becoming a necessary component in many realworld systems. The efficiency of secure twoparty protocols has improved tremendously in the last decade, making such protocols efficient enough for many realworld applications. Recently, much attention is being diverted to making secure {\em multiparty} computation (for more than two parties) truly practical as well. In particular, the last couple of years saw a resurgence of interest in constant round secure protocols, based on the multiparty garbling paradigm of Beaver et al.~(STOC 1990). Such protocols generally offer improved performance in high latency networks, such as the internet.
In this paper we consider the case where a majority of the parties are honest, and construct highly efficient constant round protocols for both the semihonest setting and the malicious setting...
______________________________________________
2016
AlmostOptimally Fair Multiparty CoinTossing with Nearly ThreeQuarters Malicious.
Bar Alon and Eran Omri
TCC (B1) 2016: 307335
Abstarct:
An αfair cointossing 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 α. Cleve [STOC 1986] has shown that if half of the parties can be corrupted, then, no rround cointossing protocol is o(1/r)fair...
______________________________________________
Optimizing SemiHonest Secure Multiparty Computation for the Internet.
Aner BenEfraim and Yehuda Lindell and Eran Omri
ACM Conference on Computer and Communications Security 2016: 578590
Abstarct:
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 \emph{twoparty} computation has advanced in leaps and bounds, with speedups of some orders of magnitude, making it fast enough to be of use in practice...
______________________________________________
Characterization of Secure Multiparty Computation Without Broadcast.
Ran Cohen and Iftach Haitner and Eran Omri and Lior Rotem.
TCC (A1) 2016: 596616
TCC version (PDF)  Draft of full version (PDF)
Abstarct:
A major challenge in the study of cryptography is characterizing the necessary and sucientassumptions required to carry out a given cryptographic task. The focus of this work is thenecessity of a broadcast channel for securely computing symmetric functionalities (where all theparties receive the same output) when one third of the parties, or more, might be corrupted.Assuming all parties are connected via a peertopeer network, but no broadcast channel (nor asecure setup phase) is available, we prove the following characterization: A symmetric nparty functionality can be securely computed facing...
______________________________________________
2015
Parallel Hashing via List Recoverability.
Iftach Haitner and Yuval Ishai and Eran Omri and Ronen Shaltiel.
Crypto (2) 2015: 173190
Crypto version (PDF)  Draft of full version (PDF)
Abstarct:
Motivated by the goal of constructing efficient hash functions, we investigate the possibility of hashing a long message by only making parallel, nonadaptive calls to a hash function on short messages. Our main result is a simple construction of a collisionresistant hash function...
______________________________________________
Rainbow matchings and algebras of sets.
G. Nivasch and E. Omri.
Graphs and Combinatorics 33(2): 473484 (2017)
EUROCOMB 2015 (Electronic Notes in Discrete Mathematics 49: 251257 (2015))
Abstarct:
Grinblat (2002) asks the following question in the context of algebras of sets: What is the smallest number ט = ט(n) such that, if A1, . . . , An are n equivalence relations on a common finite ground set X, such that for each i there are at least ט elements of X that belong to Aiequivalence classes of size larger than 1, then X has a rainbow matching—a set of 2n distinct elements a1, b1, . . . , an, bn, such that ai is Aiequivalent to bi for each i? Grinblat has shown that ט(n) ≤ 10n/3 + O( √ n). He asks whether ט(n) = 3n − 2 for all n ≥ 4. In this paper we improve the upper bound (for all large enough n) to ט(n) ≤ 16n/5 + O(1).
______________________________________________
Characterization of Fairness in Secure TwoParty Computation of Boolean Functions.
G. Asharov and A. Beimel and N. Makriyannis and E. Omri.
TCC 2015, LNCS Volume 9014, 2015, pages 199228
TCC version (PDF)  Draft of full version (PDF)
Abstarct:
Fairness is a desirable property in secure computation; informally it means that if one party gets the output of the function, then
all parties get the output. Alas, an implication of Cleve's result (STOC 86) is that when there is no honest majority, in particular in the important case of the twoparty setting, there exist Boolean functions that cannot be computed with fairness. In a surprising result, Gordon et al. (JACM 2011) showed that some interesting functions can be computed with fairness in the twoparty setting, and reopened the question of understanding which Boolean functions can be computed with fairness, and which cannot...
______________________________________________
2013
Limits on the Usefulness of Random Oracles.
Iftach Haitner, Eran Omri, and Hila Zarosim.
Journal of Cryptology (to appear)
TCC 2013, LNCS Volume 7785, 2013, pages 437456
TCC version (PDF)  Draft of full version (PDF)
Abstarct:
In the random oracle model, parties are given oracle access to a random function (i.e., a uniformly chosen function from the set of all functions), and are assumed to have unbounded computational power (though they can only make a bounded number of oracle queries). This model provides powerful properties that allow proving the security of many protocols...
______________________________________________
2012
Completeness for Symmetric TwoParty Functionalities  Revisited
Yehuda Lindell, Eran Omri, and Hila Zarosim.
ASIACRYPT 2012, volume 7658 of LNCS, Pages 116–133, 2012
Abstarct:
Understanding the minimal assumptions required for carrying out cryptographic tasks is one of the fundamental goals of theoretical cryptography. A rich body of work has been dedicated to understanding the complexity of cryptographic tasks in the context of (semihonest) secure twoparty computation. Much of this work has focused on the characterization of trivial and complete functionalities...
______________________________________________
2011
Coin Flipping with Constant Bias Implies OneWay Functions.
Iftach Haitner, Eran Omri.
SIAM Journal of Computing 43(2): 389409 (2014)
Proc. of IEEE 52nd Annual Symposium on Foundations of Computer Science (FOCS), Pages 110–119, 2011.
Full version draft (PDF)  FOCS version (PDF)
Abstract:
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 oneway functions. An important exception where the above implication is not known, however, is the case of coinflipping protocols...
______________________________________________
1/pSecure Multiparty Computation without Honest Majority and the Best of Both Worlds.
Amos Beimel, Yehuda Lindell, Eran Omri, Ilan Orlov.
CRYPTO 2011, volume 6841 of LNCS, pages 277296, 2011.
CRYPTO version (PDF)  Draft of full version (PDF)
Abstract:
A protocol for computing a functionality is secure if an adversary in this protocol cannot cause more harm than in an ideal computation, where parties give their inputs to a trusted party which returns the output of the functionality to all parties. In particular, in the ideal model such computation is fair – all parties get the output. Cleve (STOC 1986) proved that, in general, fairness is not possible without an honest majority.
______________________________________________
A Practical Application of Differential Privacy to Personalized Online Advertising.
Yehuda Lindell, Eran Omri.
Abstract:
Online advertising plays an important role in supporting many Internet services. Personalized online advertising offers marketers a way to direct ads at very specific audiences. The vast body of Internet users combined with the ease of creating and monitoring personalized advertising campaigns make online advertising an extremely strong tool for marketers...
______________________________________________
Optimizing Budget Allocation in Graphs.
Boaz BenMoshe, Eran Omri, Michael Elkin.
Proc. of the 23rd Annual Canadian Conference on Computational Geometry, (CCCG) 2011.
CCCG version PDF
Abstract:
In a classical facility location problem we consider a graph G with ﬁxed weights on the edges of G. The goal is then to ﬁnd an optimal positioning for a set of facilities on the graph with respect to some objective function. We consider a new model for facility location problems, where the weights on the graph edges are not ﬁxed, but rather should be assigned. The goal is to ﬁnd the valid assignment for which the resulting weighted graph optimizes the facility location objective function...
(Read more...)
______________________________________________
2010
Protocols for Multiparty Coin Toss with Dishonest Majority.
Amos Beimel, Eran Omri, Ilan Orlov.
Journal of Cryptology (to appear)
CRYPTO 2010, volume 6223 of LNCS, pages 538–557, 2010.
Crypto version (PDF)  Full version (PDF)
Abstract:
Cointossing protocols are protocols that generate a random bit with uniform distribution. These protocols are used as a building block in many cryptographic protocols. Cleve [STOC 1986] has shown that if at least half of the parties can be malicious, then, in any round cointossing protocol, the malicious parties can cause a bias of to the bit that the honest parties output. However, for more than two decades the best known protocols had bias , where is the number of corrupted parties...
______________________________________________
Classifying the phase transition threshold for Ackermannian function.
Eran Omri, Andreas Weiermann.
Journal of Annals of Pure and Applied Logic, 158(3):156 – 162.
Abstract:
It is well known that the Ackermann function can be defined via diagonalization from an iteration hierarchy (of Grzegorczyk type) which is built on a start function like the successor function. In this paper we study for a given start function g iteration hierarchies with a sublinear modulus h of iteration. In terms of g and h we classify the phase transition for the resulting diagonal function from being primitive recursive to being Ackermannian...
______________________________________________
2009
Matrix columns allocation problem.
Amos Beimel, Boaz BenMoshe, Yehuda BenShimol, Paz Carmi, Eldad Chai, Itzik Kitroser, Eran Omri.
Journal of Theoretical Computer Science, 410(21–23):2174–2183.
Abstract:
Orthogonal Frequency Division Multiple Access (OFDMA) transmission technique is gaining popularity as a preferred technique in the emerging broadband wireless access standards. Motivated by the OFDMA transmission technique we define the following problem...
______________________________________________
2008
Distributed Private Data Analysis: On Simultaneously Solving How and What.
Amos Beimel, Kobbi Nissim, Eran Omri.
CRYPTO 2008, volume 5157 of LNCS, pages 451–468, 2008.
Crypto version (PDF)  CoRR version
Abstract:
We examine the combination of two directions in the field of privacy concerning computations over distributed private inputs  secure function evaluation (SFE) and differential privacy.
______________________________________________
Sharp thresholds for the phase transition between primitive recursive and Ackermannian Ramsey numbers.
Menachem Kojman, Gyesik Lee, Eran Omri, Andreas Weiermann.
Journal of Combinatorial Theory, Series A, 115(6):1036–1055
Abstract:
We compute the sharp thresholds on g at which glarge and gregressive Ramsey numbers cease to be primitive recursive and become Ackermannian.
We also identify the threshold below which gregressive colorings have usual Ramsey numbers, that is, admit homogeneous, rather than just minhomogeneous sets.
Research Topics
Foundations of Cryptography
Differential Privacy
Combinatorics
Ph.D. Thesis
Title:
Phase Transition Behavior in Combinatorics and Computation.
Advisors:
Prof. Amos Beimel and Prof. Menachem Kojman, 2009.
Working Grants
The Israel Science Foundation (ISF)
The Ministry of Science, Technology and Space.