Author name cluster

Eran Omri

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

6 papers

2 author rows

TCS Journal 2022 Journal Article

On the complexity of fair coin flipping

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 / 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 / r ) -fair coin-flipping protocol. Towards answering this intriguing question, Maji and Wang [Crypto '18] have recently showed that in the random oracle model (ROM), any coin-flipping protocol can be biased by Ω ( 1 / r ). This implies that o ( 1 / r ) -fair coin-flipping protocol cannot be constructed from one-way function, or from a family of collision-resistant hash functions, in a black-box way. This result does not rule out, however, non black-box constructions, and black-box constructions based on primitives that cannot be realized in the ROM. We make a different progress towards answering above question by showing that, for any constant r ∈ N, the existence of an 1 / ( c ⋅ 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 non black-box and makes a novel use of the recent dichotomy for two-party protocols of Haitner, Nissim, Omri, Shaltiel, and Silbak [SICOMP '20] to facilitate a two-party variant of the recent attack of Beimel, Haitner, Makriyannis, and Omri [FOCS '18] on multi-party coin-flipping protocols.

Details DOI

FOCS Conference 2018 Conference Paper

Computational Two-Party Correlation: A Dichotomy for Key-Agreement Protocols

Iftach Haitner
Kobbi Nissim
Eran Omri
Ronen Shaltiel
Jad Silbak

Let π be an efficient two-party protocol that given security parameter k, both parties output single bits X k and Y k, respectively. We are interested in how (X k, Y k ) "appears" to an efficient adversary that only views the transcript T k. 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 T k, the simulator outputs a pair (X' k, Y' k ) such that (X' k, Y' k, T k ) is (somewhat) computationally indistinguishable from (X k, Y k, T k ). · 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 k, but then choose their outputs independently from some product distribution (that is determined in poly-time from T k ), - 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 ((X k, Y k )|T k = 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.

Details

FOCS Conference 2018 Conference Paper

Tighter Bounds on Multi-Party Coin Flipping via Augmented Weak Martingales and Differentially Private Sampling

Amos Beimel
Iftach Haitner
Nikolaos Makriyannis
Eran Omri

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.

Details

TCS Journal 2016 Journal Article

Optimizing budget allocation for center and median points

Boaz Ben-Moshe
Michael Elkin
Lee-Ad Gottlieb
Eran Omri

In typical graph minimization problems, we consider a graph G with fixed weights on the edges of G. The goal is then to find an optimal vertex or set of vertices with respect to some objective function, for example. We introduce a new framework for graph minimization problems, where the weights on the graph edges are not fixed, but rather must be assigned, and the weight is inversely proportional to the cost paid. The goal is to find a valid assignment for which the resulting weighted graph optimizes the objective function. We present algorithms for finding the optimal budget allocation for the center point problem and for the median point problem on trees. Our algorithms run in linear time, both for the case where a candidate vertex is given as part of the input, and for the case where finding a vertex that optimizes the solution is part of the problem. We also present a hardness result for the center point problem on complete metric graphs, followed by an O ( log 2 ⁡ ( n ) ) approximation algorithm in this setting.

Details DOI

FOCS Conference 2011 Conference Paper

Coin Flipping with Constant Bias Implies One-Way Functions

Iftach Haitner
Eran Omri

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.

Details

TCS Journal 2009 Journal Article

Matrix columns allocation problems

Amos Beimel
Boaz Ben-Moshe
Yehuda Ben-Shimol
Paz Carmi
Eldad Chai
Itzik Kitroser
Eran Omri

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: Let M be a matrix (over R ) of size a × b. Given a vector of non-negative integers C → = 〈 c 1, c 2, …, c b 〉 such that ∑ c j = a, we would like to allocate a cells in M such that (i) in each row of M there is a single allocation, and (ii) for each element c i ∈ C → there is a unique column in M which contains exactly c i allocations. Our goal is to find an allocation with minimal value, that is, the sum of all the a cells of M which were allocated is minimal. The nature of the suggested new problem is investigated in this paper. Efficient algorithms are suggested for some interesting cases. For other cases of the problem, NP-hardness proofs are given followed by inapproximability results.

Details DOI