Iftach Haitner

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.

STOC Conference 2022 Conference Paper

On the complexity of two-party differential privacy

• Iftach Haitner
• Noam Mazor
• Jad Silbak
• Eliad Tsfadia

In distributed differential privacy, the parties perform analysis over their joint data while preserving the privacy for both datasets. Interestingly, for a few fundamental two-party functions such as inner product and Hamming distance, the accuracy of the distributed solution lags way behind what is achievable in the client-server setting. McGregor, Mironov, Pitassi, Reingold, Talwar, and Vadhan [FOCS ’10] proved that this gap is inherent, showing upper bounds on the accuracy of (any) distributed solution for these functions. These limitations can be bypassed when settling for computational differential privacy, where the data is differentially private only in the eyes of a computationally bounded observer, using oblivious transfer. We prove that the use of public-key cryptography is necessary for bypassing the limitation of McGregor et al., showing that a non-trivial solution for the inner product, or the Hamming distance, implies the existence of a key-agreement protocol. Our bound implies a combinatorial proof for the fact that non-Boolean inner product of independent (strong) Santha-Vazirani sources is a good condenser. We obtain our main result by showing that the inner-product of a (single, strong) SV source with a uniformly random seed is a good condenser, even when the seed and source are dependent.

FOCS Conference 2020 Conference Paper

A Tight Lower Bound on Adaptively Secure Full-Information Coin Flip

• Iftach Haitner
• Yonatan Karidi-Heller

In a distributed coin-flipping protocol, Blum [ACM Transactions on Computer Systems '83], the parties try to output a common (close to) uniform bit, even when some adversarially chosen parties try to bias the common output. In an adaptively secure full-information coin flip, Ben-Or and Linial [FOCS '85], the parties communicate over a broadcast channel and a computationally unbounded adversary can choose which parties to corrupt along the protocol execution. Ben-Or and Linial proved that the n-party majority protocol is resilient to O(√n) corruptions (ignoring poly-logarithmic factors), and conjectured this is a tight upper bound for any n-party protocol (of any round complexity). Their conjecture was proved to be correct for single-turn (each party sends a single message) single-bit (a message is one bit) protocols Lichtenstein, Linial, and Saks [Combinatorica '89], symmetric protocols Goldwasser, Tauman Kalai, and Park [ICALP '15], and recently for (arbitrary message length) single-turn protocols Tauman Kalai, Komargodski, and Raz [DISC '18]. Yet, the question for many-turn protocols was left completely open. In this work we close the above gap, proving that no n-party protocol (of any round complexity) is resilient to ω(√n) (adaptive) corruptions.

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.

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.

SODA Conference 2017 Conference Paper

Fair Coin Flipping: Tighter Analysis and the Many-Party Case

• Niv Buchbinder
• Iftach Haitner
• Nissan Levi
• Eliad Tsfadia

In a multi-party fair coin-flipping protocol, the parties output a common (close to) unbiased bit, even when some corrupted parties try to bias the output. In this work we focus on the case of dishonest majority, ie at least half of the parties can be corrupted. [19] [STOC 1986] has shown that in any m -round coin-flipping protocol the corrupted parties can bias the honest parties’ common output bit by Θ(1/m). For more than two decades the best known coin-flipping protocols against majority was the protocol of [9] [Manuscript 1985], who presented a t -party, m -round protocol with bias This was changed by the breakthrough result of [42] [TCC 2009], who constructed an m -round, two-party coin-flipping protocol with optimal bias Θ(1/m). Recently, [32] [STOC 14] constructed an m -round, three -party coin-flipping protocol with bias O (log 3 m/m). Still for the case of more than three parties, against arbitrary number of corruptions, the best known protocol remained the protocol of [9]. We make a step towards eliminating the above gap, presenting a t -party, m -round coin-flipping protocol, with bias This improves upon the protocol of [9] for any t ≤ 1/2 · log log m, and in particular for t ∊ O (1), this yields an protocol. For the three-party case, this yields an protocol, improving over the the O (log 3 m/m)-bias protocol of [32]. Our protocol generalizes that of [32], by presenting an appropriate “defense protocols” for the remaining parties to interact in, in the case that some parties abort or caught cheating ([32] only presented a two-party defense protocol, which limits their final protocol to handle three parties). We analyze our new protocols by presenting a new paradigm for analyzing fairness of coin-flipping protocols. We map the set of adversarial strategies that try to bias the honest parties outcome in the protocol to the set of the feasible solutions of a linear program. The gain each strategy achieves is the value of the corresponding solution. We then bound the the optimal value of the linear program by constructing a feasible solution to its dual.

STOC Conference 2014 Conference Paper

An almost-optimally fair three-party coin-flipping protocol

• Iftach Haitner
• Eliad Tsfadia

STOC Conference 2014 Conference Paper

Coin flipping of any constant bias implies one-way functions

• Itay Berman
• Iftach Haitner
• Aris Tentes

We show that the existence of a coin-flipping protocol safe against any non-trivial constant bias (e.g., .499) implies the existence of one-way functions. This improves upon a recent result of Haitner and Omri [FOCS '11], who proved this implication for protocols with bias [EQUATION] -- o (1) ≈ .207. Unlike the result of Haitner and Omri, our result also holds for w eak coin-flipping protocols.

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.

STOC Conference 2010 Conference Paper

Efficiency improvements in constructing pseudorandom generators from one-way functions

• Iftach Haitner
• Omer Reingold
• Salil P. Vadhan

We give a new construction of pseudorandom generators from any one-way function. The construction achieves better parameters and is simpler than that given in the seminal work of Hastad, Impagliazzo, Levin, and Luby [SICOMP '99]. The key to our construction is a new notion of "next-block pseudoentropy", which is inspired by the notion of "inaccessible entropy" recently introduced in [Haitner, Reingold, Vadhan, Wee, STOC '09]. An additional advantage over previous constructions is that our pseudorandom generators are parallelizable and invoke the one-way function in a non-adaptive manner. Using [Applebaum, Ishai, Kushilevitz, SICOMP '06], this implies the existence of pseudorandom generators in NC^0 based on the existence of one-way functions in NC^1.

FOCS Conference 2009 Conference Paper

A Parallel Repetition Theorem for Any Interactive Argument

• Iftach Haitner

The question of whether or not parallel repetition reduces the soundness error is a fundamental question in the theory of protocols. While parallel repetition reduces (at an exponential rate) the error in interactive proofs and (at a weak exponential rate) in special cases of interactive arguments (e. g. , 3-message protocols-Bellare, Impagliazzo and Naor [FOCS '97], and public-coin protocols-Haastad, Pass, Pietrzak and Wikstrom [Manuscript '08]), Bellare et. al gave an example of interactive arguments for which parallel repetition does not reduce the soundness error at all. We show that by slightly modifying any interactive argument, in a way that preserves its completeness and only slightly deteriorates its soundness, we get a protocol for which parallel repetition does reduce the error at a weak exponential rate. In this modified version, the verifier flips at the beginning of each round an (1 - 1/4 m), 1/4 m) biased coin (i. e. , 1 is tossed with probability 1/4 m), where m is the round complexity of the (original) protocol. If the coin is one, the verifier halts the interaction and accepts, otherwise it sends the same message that the original verifier would. At the end of the protocol (if reached), the verifier accepts if and only if the original verifier would.

STOC Conference 2009 Conference Paper

Inaccessible entropy

• Iftach Haitner
• Omer Reingold
• Salil P. Vadhan
• Hoeteck Wee

We put forth a new computational notion of entropy, which measures the (in)feasibility of sampling high entropy strings that are consistent with a given protocol. Specifically, we say that the i'th round of a protocol (A,B) has *accessible entropy* at most k, if no polynomial-time strategy A* can generate messages for A such that the entropy of its message in the i'th round has entropy greater than k when conditioned both on prior messages of the protocol and on prior coin tosses of A*. We say that the protocol has *inaccessible entropy* if the total accessible entropy (summed over the rounds) is noticeably smaller than the real entropy of A's messages, conditioned only on prior messages (but not the coin tosses of A). As applications of this notion, we -- Give a much simpler and more efficient construction of statistically hiding commitment schemes from arbitrary one-way functions. -- Prove that constant-round statistically hiding commitments are necessary for constructing constant-round zero-knowledge proof systems for NP that remain secure under parallel composition (assuming the existence of one-way functions).

FOCS Conference 2007 Conference Paper

Finding Collisions in Interactive Protocols - A Tight Lower Bound on the Round Complexity of Statistically-Hiding Commitments

• Iftach Haitner
• Jonathan J. Hoch
• Omer Reingold
• Gil Segev 0001

We study the round complexity of various cryptographic protocols. Our main result is a tight lower bound on the round complexity of any fully-black-box construction of a statistically-hiding commitment scheme from oneway permutations, and even front trapdoor permutations. This lower bound matches the round complexity of the statistically-hiding commitment scheme due to Naor, Ostrovsky, Venkatesan and Yung (CRYPTO '92). As a corollary, we derive similar tight lower bounds for several other ctyptographicprotocols, such as single-server private information retrieval, interactive hashing, and oblivious transfer that guarantees statistical security for one of the parties. Our techniques extend the collision-finding oracle due to Simon (EUROCRYPT '98) to the setting of interactive protocols (our extension also implies an alternative proof for the main property of the original oracle). In addition, we substantially extend the reconstruction paradigm of Gennaro and Trevisan (FOCS '00). In both cases, our extensions are quite delicate and may be found useful in proving additional black-box separation results.

STOC Conference 2007 Conference Paper

Statistically-hiding commitment from any one-way function

• Iftach Haitner
• Omer Reingold

We give a construction of statistically-hiding commitment schemes (ones where the hiding propertyholds information theoretically), based on the minimal cryptographic assumption that one-way functions exist. Our construction employs two-phase commitment schemes, recently constructed by Nguyen, Ong and Vadhan (FOCS '06), and universal one-way hash functions introduced and constructedby Naor and Yung (STOC '89) and Rompel (STOC '90).