2013
Limits on the Usefulness of Random Oracles.
Iftach Haitner, Eran Omri, and Hila Zarosim.
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 (to appear)
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.
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...
______________________________________________
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 number.
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.
The Israel Science Foundation (ISF)
The Ministry of Science, Technology and Space.