2021
Large Scale, Actively Secure Computation from LPN and Free-XOR Garbled Circuits.
Aner Ben-Efraim and Kelong Cong and Eran Omri and Emmanuela Orsini and Nigel P. Smart and Eduardo Soria-Vazquez
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 free-XOR technique, and which has communication complexity O(n)O(n) per party. This improves on a protocol of Ben-Efraim, Lindell and Omri which only achieved passive security, without support for free-XOR. Our construction is based on a new variant of LPN-based 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 Maliciously-Secure Private Set Intersection.
Aner Ben-Efraim and Olga Nissenbaum and Eran Omri and Anat Paskin-Cherniavsky.
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., COVID-19 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 semi-honest 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 maliciously-secure multiparty PSI protocol.
2020
MPC with Friends and Foes
Bar Alon and Eran Omri and Anat Paskin-Cherniavsky.
CRYPTO 2020
Preliminary full version [eprint]
Abstarct:
IIn their breakthrough result, Moran, Naor, and Segev [Journal of Cryptology '16] show how to construct an r-round-round two-party coin-flipping 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 one-way function. An intriguing open question is whether oblivious transfer, or more generally "public-key primitives", is required for an o(1/r)-bias coin flipping. This question was partially answered in the black-box settings by Dachman-Soled et al. [11] [TCC '11] and Dachman-Soled et al. [12] [TCC '14], who showed that restricted types of fully black-box reductions cannot established such o(1/r)-bias coin-flipping protocol from one-way functions.
(Read more...)
______________________________________________
On the Power of an Honest Majority in Three-Party 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 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.
______________________________________________
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 r-round-round two-party coin-flipping 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 one-way function. An intriguing open question is whether oblivious transfer, or more generally "public-key primitives", is required for an o(1/r)-bias coin flipping. This question was partially answered in the black-box settings by Dachman-Soled et al. [11] [TCC '11] and Dachman-Soled et al. [12] [TCC '14], who showed that restricted types of fully black-box reductions cannot established such o(1/r)-bias coin-flipping protocol from one-way functions.
We make progress towards answering the above question, showing that for any (constant) r ∈ N, the existence of an r-round o(1/r)-bias coin flipping protcol implies the existence of an infinitely-often key-agreement protocol. Our reduction is non black-box, and makes a novel use of the recent dichotomy for two-party protocols of Haitner et al. [ECCC '18] to facilitate, for the two-party case, the recent attack of Beimel et al [ECCC '17] on multi-party coin-flipping 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 r-round-round two-party coin-flipping 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 one-way function. An intriguing open question is whether oblivious transfer, or more generally "public-key primitives", is required for an o(1/r)-bias coin flipping. This question was partially answered in the black-box settings by Dachman-Soled et al. [11] [TCC '11] and Dachman-Soled et al. [12] [TCC '14], who showed that restricted types of fully black-box reductions cannot established such o(1/r)-bias coin-flipping protocol from one-way functions.
We make progress towards answering the above question, showing that for any (constant) r ∈ N, the existence of an r-round o(1/r)-bias coin flipping protcol implies the existence of an infinitely-often key-agreement protocol. Our reduction is non black-box, and makes a novel use of the recent dichotomy for two-party protocols of Haitner et al. [ECCC '18] to facilitate, for the two-party case, the recent attack of Beimel et al [ECCC '17] on multi-party coin-flipping protocols.
______________________________________________
Computational Two-Party Correlation.
Iftach Haitner and Eran Omri and Kobbi Nissim and Ronen Shaltiel and Jad Silbak
FOCS 2018
Abstarct:
We prove a dichotomy theorem for two-party protocols, and show that for every poly-time two-party protocol with single-bit output, at least one of following holds:
-
The protocol can be used to construct a key-agreement 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 key-agreement, then its output distribution (X; Y; T) is trivial: it can be simulated non-interactively 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 Multi-Party 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 r-round coin-flipping protocol can be efficiently biassed by Ω(1/r). The above 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) byHaitner and Tsfadia [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 Θ(n/√r) achieved by the majority protocol of Awerbuch, Blum, Chor, Goldwasser, and Micali [Manuscript '85].
(Read more...)
______________________________________________
Efficient Scalable Multiparty Private Set-Intersection 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
real-life scenarios. Much research was dedicated to the construction of
PSI-tailored concretely efficient protocols for the case of two-party 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 Constant-Round MPC via Garbled Circuits.
Aner Ben-Efraim 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 two-party case. In contrast, in the multiparty case, progress has been much slower, even for the case of semi-honest adversaries.
In this paper, we consider the case of constant-round 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 semi-honest adversaries (Ben-Efraim 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 Ben-Efraim and and Eran Omri
Latincrypt 2017
Abstarct:
Secure multiparty computation is becoming a necessary component in many real-world systems. The efficiency of secure two-party protocols has improved tremendously in the last decade, making such protocols efficient enough for many real-world 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 semi-honest setting and the malicious setting...
______________________________________________
2016
Almost-Optimally Fair Multiparty Coin-Tossing with Nearly Three-Quarters Malicious.
Bar Alon and Eran Omri
TCC (B1) 2016: 307-335
Abstarct:
An α-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 α. Cleve [STOC 1986] has shown that if half of the parties can be corrupted, then, no r-round coin-tossing protocol is o(1/r)-fair...
______________________________________________
Optimizing Semi-Honest Secure Multiparty Computation for the Internet.
Aner Ben-Efraim and Yehuda Lindell and Eran Omri
ACM Conference on Computer and Communications Security 2016: 578-590
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{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...
______________________________________________
Characterization of Secure Multiparty Computation Without Broadcast.
Ran Cohen and Iftach Haitner and Eran Omri and Lior Rotem.
TCC (A1) 2016: 596-616
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 peer-to-peer network, but no broadcast channel (nor asecure setup phase) is available, we prove the following characterization: A symmetric n-party 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: 173-190
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, non-adaptive calls to a hash function on short messages. Our main result is a simple construction of a collision-resistant hash function...
______________________________________________
Rainbow matchings and algebras of sets.
G. Nivasch and E. Omri.
Graphs and Combinatorics 33(2): 473-484 (2017)
EUROCOMB 2015 (Electronic Notes in Discrete Mathematics 49: 251-257 (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 Ai-equivalence 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 Ai-equivalent 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 Two-Party Computation of Boolean Functions.
G. Asharov and A. Beimel and N. Makriyannis and E. Omri.
TCC 2015, LNCS Volume 9014, 2015, pages 199-228
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 two-party 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 two-party setting, and re-opened 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 437-456
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 Two-Party 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 (semi-honest) secure two-party computation. Much of this work has focused on the characterization of trivial and complete functionalities...
______________________________________________
2011
Coin Flipping with Constant Bias Implies One-Way Functions.
Iftach Haitner, Eran Omri.
SIAM Journal of Computing 43(2): 389-409 (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 one-way functions. An important exception where the above implication is not known, however, is the case of coin-flipping protocols...
______________________________________________
1/p-Secure 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 277-296, 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 Ben-Moshe, 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 fixed weights on the edges of G. The goal is then to find 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 fixed, but rather should be assigned. The goal is to find 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:
Coin-tossing 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 coin-tossing 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 sub-linear 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 Ben-Moshe, Yehuda Ben-Shimol, 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 g-large and g-regressive Ramsey numbers cease to be primitive recursive and become Ackermannian.
We also identify the threshold below which g-regressive colorings have usual Ramsey numbers, that is, admit homogeneous, rather than just min-homogeneous 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.